X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fopt%2Fopt_blocks.c;h=0154be69d5c30eefdfa3fa34d3e4b3b687044dc6;hb=7547cf525ad54f59d2dc3f39d4b257911c94989b;hp=4ad1b952ef16821794efb31221f0714be6acb724;hpb=4803d434aae007f6506553c8d714c31f503ec78c;p=libfirm diff --git a/ir/opt/opt_blocks.c b/ir/opt/opt_blocks.c index 4ad1b952e..0154be69d 100644 --- a/ir/opt/opt_blocks.c +++ b/ir/opt/opt_blocks.c @@ -23,13 +23,13 @@ * @author Michael Beck * @version $Id$ * - * This phase find congruent blocks. Works currently for - * predecessors of the end block only. + * 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" @@ -38,9 +38,11 @@ #include "trouts.h" #include "irgwalk.h" #include "set.h" +#include "irpass.h" #include "debug.h" -/* define this for gneral block shaping */ +/* define this for general block shaping: congruent blocks + are found not only before the end block but anywhere in the graph */ #define GENERAL_SHAPE typedef struct partition_t partition_t; @@ -61,7 +63,7 @@ struct opcode_key_t { 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. */ @@ -110,7 +112,7 @@ struct environment_t { struct obstack obst; /** obstack for temporary data */ }; -/** A node, input index pair. */ +/** A (node, input index) pair. */ struct pair_t { pair_t *next; /**< Points to the next pair entry. */ ir_node *irn; /**< The IR-node. */ @@ -158,7 +160,8 @@ DEBUG_ONLY(static unsigned part_nr = 0); /** * Dump partition to output. */ -static void dump_partition(const char *msg, const partition_t *part) { +static void dump_partition(const char *msg, const partition_t *part) +{ const block_t *block; int first = 1; @@ -173,7 +176,8 @@ static void dump_partition(const char *msg, const partition_t *part) { /** * Dumps a list. */ -static void dump_list(const char *msg, const block_t *block) { +static void dump_list(const char *msg, const block_t *block) +{ const block_t *p; int first = 1; @@ -192,7 +196,8 @@ static void dump_list(const char *msg, const block_t *block) { /** * Compare two pointer values of a listmap. */ -static int listmap_cmp_ptr(const void *elt, const void *key, size_t size) { +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; @@ -205,7 +210,8 @@ static int listmap_cmp_ptr(const void *elt, const void *key, size_t size) { * * @param map the listmap */ -static void listmap_init(listmap_t *map) { +static void listmap_init(listmap_t *map) +{ map->map = new_set(listmap_cmp_ptr, 16); map->values = NULL; } /* listmap_init */ @@ -215,7 +221,8 @@ static void listmap_init(listmap_t *map) { * * @param map the listmap */ -static void listmap_term(listmap_t *map) { +static void listmap_term(listmap_t *map) +{ del_set(map->map); } /* listmap_term */ @@ -227,7 +234,8 @@ static void listmap_term(listmap_t *map) { * * @return the associated listmap entry for the given id */ -static listmap_entry_t *listmap_find(listmap_t *map, void *id) { +static listmap_entry_t *listmap_find(listmap_t *map, void *id) +{ listmap_entry_t key, *entry; key.id = id; @@ -250,7 +258,8 @@ 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) { +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 */ @@ -258,7 +267,8 @@ static unsigned opcode_hash(const opcode_key_t *entry) { /** * Compare two entries in the opcode map. */ -static int cmp_opcode(const void *elt, const void *key, size_t size) { +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; @@ -272,11 +282,12 @@ static int cmp_opcode(const void *elt, const void *key, size_t size) { * Creates a new empty partition and put in on the * partitions list. * - * @param meet_block the control flow meet block of thi partition + * @param meet_block the control flow meet block of this partition * @param env the environment */ -static partition_t *create_partition(ir_node *meet_block, environment_t *env) { - partition_t *part = obstack_alloc(&env->obst, sizeof(*part)); +static partition_t *create_partition(ir_node *meet_block, environment_t *env) +{ + partition_t *part = OALLOC(&env->obst, partition_t); INIT_LIST_HEAD(&part->blocks); part->meet_block = meet_block; @@ -294,8 +305,9 @@ static partition_t *create_partition(ir_node *meet_block, environment_t *env) { * @param partition the partition to add to * @param env the environment */ -static block_t *create_block(ir_node *block, int meet_input, partition_t *partition, environment_t *env) { - block_t *bl = obstack_alloc(&env->obst, sizeof(*bl)); +static block_t *create_block(ir_node *block, int meet_input, partition_t *partition, environment_t *env) +{ + block_t *bl = OALLOC(&env->obst, block_t); set_irn_link(block, bl); @@ -326,8 +338,9 @@ static block_t *create_block(ir_node *block, int meet_input, partition_t *partit * @param block the block to add to * @param env the environment */ -static node_t *create_node(ir_node *irn, block_t *block, environment_t *env) { - node_t *node = obstack_alloc(&env->obst, sizeof(*node)); +static node_t *create_node(ir_node *irn, block_t *block, environment_t *env) +{ + node_t *node = OALLOC(&env->obst, node_t); node->node = irn; node->is_input = 0; @@ -345,8 +358,9 @@ static node_t *create_node(ir_node *irn, block_t *block, environment_t *env) { * @param idx the index of the block input in node's predecessors * @param env the environment */ -static void add_pair(block_t *block, ir_node *irn, int idx, environment_t *env) { - pair_t *pair = obstack_alloc(&env->obst, sizeof(*pair)); +static void add_pair(block_t *block, ir_node *irn, int idx, environment_t *env) +{ + pair_t *pair = OALLOC(&env->obst, pair_t); pair->next = block->input_pairs; pair->irn = irn; @@ -363,8 +377,9 @@ static void add_pair(block_t *block, ir_node *irn, int idx, environment_t *env) * @param phi the Phi node * @param env the environment */ -static void add_phi(block_t *block, ir_node *phi, environment_t *env) { - phi_t *node = obstack_alloc(&env->obst, sizeof(*node)); +static void add_phi(block_t *block, ir_node *phi, environment_t *env) +{ + phi_t *node = OALLOC(&env->obst, phi_t); node->next = block->phis; node->phi = phi; @@ -376,7 +391,8 @@ static void add_phi(block_t *block, ir_node *phi, environment_t *env) { /** * Creates an opcode from a node. */ -static opcode_key_t *opcode(const node_t *node, environment_t *env) { +static opcode_key_t *opcode(const node_t *node, environment_t *env) +{ opcode_key_t key, *entry; ir_node *irn = node->node; @@ -409,8 +425,14 @@ static opcode_key_t *opcode(const node_t *node, environment_t *env) { case iro_Conv: key.u.intVal = get_Conv_strict(irn); break; + case iro_Load: + key.mode = get_Load_mode(irn); + break; case iro_Div: - key.u.intVal = is_Div_remainderless(irn); + key.u.intVal = get_Div_no_remainder(irn); + break; + case iro_Builtin: + key.u.intVal = get_Builtin_kind(irn); break; default: break; @@ -429,7 +451,8 @@ static opcode_key_t *opcode(const node_t *node, environment_t *env) { * * @return a new partition containing the nodes of g */ -static partition_t *split(partition_t *Z, block_t *g, environment_t *env) { +static partition_t *split(partition_t *Z, block_t *g, environment_t *env) +{ partition_t *Z_prime; block_t *block; unsigned n = 0; @@ -462,7 +485,8 @@ static partition_t *split(partition_t *Z, block_t *g, environment_t *env) { /** * Return non-zero if pred should be tread as a input node. */ -static int is_input_node(ir_node *pred, ir_node *irn, int index) { +static int is_input_node(ir_node *pred, ir_node *irn, int index) +{ /* for now, do NOT turn direct calls into indirect one */ if (index != 1) return 1; @@ -479,7 +503,8 @@ static int is_input_node(ir_node *pred, ir_node *irn, int index) { * @param part the partition * @param env the environment */ -void propagate_blocks(partition_t *part, environment_t *env) { +static void propagate_blocks(partition_t *part, environment_t *env) +{ block_t *ready_blocks = NULL; unsigned n_ready = 0; block_t *bl, *next; @@ -544,7 +569,7 @@ void propagate_blocks(partition_t *part, environment_t *env) { DB((dbg, LEVEL_3, " propagate Input %+F\n", node->node)); } - /* Add bl to map[opcode(bl)]. */ + /* Add bl to map[opcode(n)]. */ id = opcode(node, env); entry = listmap_find(&map, id); bl->next = entry->list; @@ -590,7 +615,8 @@ void propagate_blocks(partition_t *part, environment_t *env) { * * @param env the environment */ -void propagate(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) { @@ -606,7 +632,8 @@ void propagate(environment_t *env) { /** * Map a block to the phi[block->input] live-trough. */ -static void *live_throughs(const block_t *bl, const ir_node *phi) { +static void *live_throughs(const block_t *bl, const ir_node *phi) +{ ir_node *input = get_Phi_pred(phi, bl->meet_input); /* If this input is inside our block, this @@ -624,7 +651,8 @@ 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; @@ -678,7 +706,8 @@ void propagate_blocks_live_troughs(partition_t *part, environment_t *env) { * * @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) { @@ -697,7 +726,8 @@ void propagate_live_troughs(environment_t *env) { * * @param part the partition to process */ -static void apply(ir_graph *irg, partition_t *part) { +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; @@ -820,7 +850,7 @@ static void apply(ir_graph *irg, partition_t *part) { if (is_op_forking(cfop)) { /* a critical edge */ ir_node *block = new_r_Block(irg, 1, &ins[i]); - ir_node *jmp = new_r_Jmp(irg, block); + ir_node *jmp = new_r_Jmp(block); ins[i] = jmp; } } @@ -839,7 +869,7 @@ static void apply(ir_graph *irg, partition_t *part) { for (repr_pair = repr->input_pairs; repr_pair != NULL; repr_pair = repr_pair->next) { ir_node *input = get_irn_n(repr_pair->irn, repr_pair->index); ir_mode *mode = get_irn_mode(input); - ir_node *phi = new_r_Phi(current_ir_graph, block, n, repr_pair->ins, mode); + ir_node *phi = new_r_Phi(block, n, repr_pair->ins, mode); set_irn_n(repr_pair->irn, repr_pair->index, phi); DEL_ARR_F(repr_pair->ins); @@ -909,7 +939,8 @@ continue_outer: * @param end_block the end block * @param env the environment */ -static void partition_for_end_block(ir_node *end_block, environment_t *env) { +static void partition_for_end_block(ir_node *end_block, environment_t *env) +{ partition_t *part = create_partition(end_block, env); ir_node *end; int i; @@ -931,7 +962,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; @@ -962,7 +993,8 @@ static void partition_for_end_block(ir_node *end_block, environment_t *env) { * @param n_preds number of elements in preds * @param env the environment */ -static void partition_for_block(ir_node *block, pred_t preds[], int n_preds, environment_t *env) { +static void partition_for_block(ir_node *block, pred_t preds[], int n_preds, environment_t *env) +{ partition_t *part = create_partition(block, env); int i; @@ -988,7 +1020,8 @@ static void partition_for_block(ir_node *block, pred_t preds[], int n_preds, env * Walker: clear the links of all block phi lists and normal * links. */ -static void clear_phi_links(ir_node *irn, void *env) { +static void clear_phi_links(ir_node *irn, void *env) +{ (void) env; if (is_Block(irn)) { set_Block_phis(irn, NULL); @@ -999,7 +1032,8 @@ static void clear_phi_links(ir_node *irn, void *env) { /** * Walker, detect live-out nodes. */ -static void find_liveouts(ir_node *irn, void *ctx) { +static void find_liveouts(ir_node *irn, void *ctx) +{ environment_t *env = ctx; ir_node **live_outs = env->live_outs; ir_node *this_block; @@ -1041,12 +1075,13 @@ static void find_liveouts(ir_node *irn, void *ctx) { /** * Check if the current block is the meet block of a its predecessors. */ -static void check_for_cf_meet(ir_node *block, void *ctx) { +static void check_for_cf_meet(ir_node *block, void *ctx) +{ environment_t *env = 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; @@ -1081,9 +1116,10 @@ static void check_for_cf_meet(ir_node *block, void *ctx) { /** * Compare two nodes for root ordering. */ -static int cmp_nodes(const void *a, const void *b) { - ir_node *const *pa = a; - ir_node *const *pb = b; +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 *irn_a = *pa; const ir_node *irn_b = *pb; ir_opcode code_a = get_irn_opcode(irn_a); @@ -1112,7 +1148,8 @@ static int cmp_nodes(const void *a, const void *b) { /** * Add the roots to all blocks. */ -static void add_roots(ir_graph *irg, environment_t *env) { +static void add_roots(ir_graph *irg, environment_t *env) +{ unsigned idx, n = get_irg_last_idx(irg); ir_node **live_outs = env->live_outs; block_t *bl; @@ -1134,7 +1171,7 @@ static void add_roots(ir_graph *irg, environment_t *env) { } /* * Now sort the roots to normalize them as good as possible. - * Else, we will split identical blocks if we start which different roots + * 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); @@ -1159,15 +1196,13 @@ static void add_roots(ir_graph *irg, environment_t *env) { #endif /* GENERAL_SHAPE */ /* Combines congruent end blocks into one. */ -int shape_blocks(ir_graph *irg) { - ir_graph *rem; +int shape_blocks(ir_graph *irg) +{ 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"); @@ -1236,14 +1271,20 @@ int shape_blocks(ir_graph *irg) { /* Calls might be removed. */ set_trouts_inconsistent(); + } - // dump_ir_block_graph(irg, "-after"); + for (bl = env.all_blocks; bl != NULL; bl = bl->all_next) { + DEL_ARR_F(bl->roots); } 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 */