X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fopt%2Fopt_blocks.c;h=4ad1b952ef16821794efb31221f0714be6acb724;hb=1a4bb21b7aa32f0bcd282d4c1cdb144aca601fa9;hp=d4612fdb6458332895d96baf0b70aec0130dee0a;hpb=3badef5f486504db409ac42baa2d75ae70377dc5;p=libfirm diff --git a/ir/opt/opt_blocks.c b/ir/opt/opt_blocks.c index d4612fdb6..4ad1b952e 100644 --- a/ir/opt/opt_blocks.c +++ b/ir/opt/opt_blocks.c @@ -29,13 +29,20 @@ */ #include "config.h" #include "ircons.h" +#include "iroptimize.h" #include "irgmod.h" #include "irgraph_t.h" #include "irnode_t.h" #include "iropt_t.h" +#include "array_t.h" +#include "trouts.h" +#include "irgwalk.h" #include "set.h" #include "debug.h" +/* define this for gneral block shaping */ +#define GENERAL_SHAPE + typedef struct partition_t partition_t; typedef struct block_t block_t; typedef struct node_t node_t; @@ -44,6 +51,7 @@ typedef struct phi_t phi_t; typedef struct opcode_key_t opcode_key_t; typedef struct listmap_entry_t listmap_entry_t; typedef struct environment_t environment_t; +typedef struct pred_t pred_t; /** An opcode map key. */ struct opcode_key_t { @@ -51,8 +59,12 @@ struct opcode_key_t { 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 */ + long proj; /**< For Proj nodes, its proj number */ + ir_entity *ent; /**< For Sel nodes, its entity */ + 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. */ } u; }; @@ -61,6 +73,7 @@ struct partition_t { list_head part_list; /**< Double linked list of partitions. */ list_head blocks; /**< List of blocks in this partition. */ unsigned n_blocks; /**< Number of block in this partition. */ + ir_node *meet_block; /**< The control flow meet block of this partition. */ #ifdef DEBUG_libfirm unsigned nr; /**< For debugging: number of this partition. */ #endif @@ -72,16 +85,18 @@ struct block_t { list_head nodes; /**< Wait-queue of nodes that must be checked for congruence. */ block_t *next; /**< Next block of a split list. */ ir_node *block; /**< Pointer to the associated IR-node block. */ - node_t *roots; /**< The list of all root nodes. */ + ir_node **roots; /**< An array of all root nodes. */ + node_t *cf_root; /**< The control flow root node of this block. */ pair_t *input_pairs; /**< The list of inputs to this block. */ phi_t *phis; /**< The list of Phis in this block. */ + block_t *all_next; /**< Links all created blocks. */ + int meet_input; /**< Input number of this block in the meet-block. */ }; /** A node. */ struct node_t { list_head node_list; /**< Double linked list of block inside a partition. */ ir_node *node; /**< Pointer to the associated IR-node or NULL for block inputs. */ - node_t *next; /**< Link to the next node in the root set. */ char is_input; /**< Set if this node is an input from other block. */ }; @@ -90,6 +105,8 @@ struct environment_t { list_head partitions; /**< list of partitions. */ list_head ready; /**< list of ready partitions. */ set *opcode2id_map; /**< The opcodeMode->id map. */ + ir_node **live_outs; /**< Live out only nodes. */ + block_t *all_blocks; /**< List of all created blocks. */ struct obstack obst; /** obstack for temporary data */ }; @@ -108,6 +125,12 @@ struct phi_t { ir_node **ins; /**< A new in array once allocated. */ }; +/** Describes a predecessor input. */ +struct pred_t { + ir_node *pred; /**< The predecessor. */ + int index; /**< Its input index. */ +}; + /** * An entry in the list_map. */ @@ -123,6 +146,8 @@ typedef struct listmap_t { listmap_entry_t *values; /**< List of all values in the map. */ } listmap_t; +#define get_Block_entry(block) ((block_t *)get_irn_link(block)) + /** The debug module handle. */ DEBUG_ONLY(static firm_dbg_module_t *dbg;) @@ -137,12 +162,12 @@ static void dump_partition(const char *msg, const partition_t *part) { const block_t *block; int first = 1; - DB((dbg, LEVEL_2, "%s part%u (%u) {\n ", msg, part->nr, part->n_blocks)); + 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) { DB((dbg, LEVEL_2, "%s%+F", first ? "" : ", ", block->block)); first = 0; } - DB((dbg, LEVEL_2, "\n}\n")); + DB((dbg, LEVEL_2, "\n }\n")); } /* dump_partition */ /** @@ -152,12 +177,12 @@ static void dump_list(const char *msg, const block_t *block) { const block_t *p; int first = 1; - DB((dbg, LEVEL_3, "%s = {\n ", msg)); + DB((dbg, LEVEL_3, " %s = {\n ", msg)); for (p = block; p != NULL; p = p->next) { DB((dbg, LEVEL_3, "%s%+F", first ? "" : ", ", p->block)); first = 0; } - DB((dbg, LEVEL_3, "\n}\n")); + DB((dbg, LEVEL_3, "\n }\n")); } /* do_dump_list */ #else #define dump_partition(msg, part) @@ -226,7 +251,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) { - return (entry->mode - (ir_mode *)0) * 9 + entry->code + entry->u.proj * 3 + HASH_PTR(entry->u.ent) + entry->arity; + /* 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 */ /** @@ -239,75 +265,77 @@ static int cmp_opcode(const void *elt, const void *key, size_t size) { (void) size; return o1->code != o2->code || o1->mode != o2->mode || o1->arity != o2->arity || - o1->u.proj != o2->u.proj || o1->u.ent != o2->u.ent; + o1->u.proj != o2->u.proj || o1->u.addr != o2->u.addr; } /* cmp_opcode */ /** - * Creates a new empty partition. + * Creates a new empty partition and put in on the + * partitions list. + * + * @param meet_block the control flow meet block of thi partition + * @param env the environment */ -static partition_t *create_partition(environment_t *env) { +static partition_t *create_partition(ir_node *meet_block, environment_t *env) { partition_t *part = obstack_alloc(&env->obst, sizeof(*part)); INIT_LIST_HEAD(&part->blocks); - part->n_blocks = 0; + part->meet_block = meet_block; + part->n_blocks = 0; DEBUG_ONLY(part->nr = part_nr++); list_add_tail(&part->part_list, &env->partitions); return part; } /* create_partition */ /** - * Allocate a new block. + * Allocate a new block in the given partition. * - * @param block the IR-node - * @param env the environment + * @param block the IR-node + * @param meet_input Input number of this block in the meet-block + * @param partition the partition to add to + * @param env the environment */ -static block_t *create_block(ir_node *block, environment_t *env) { +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)); + set_irn_link(block, bl); + INIT_LIST_HEAD(&bl->nodes); bl->next = NULL; bl->block = block; - bl->roots = NULL; + bl->roots = NEW_ARR_F(ir_node *, 0); + bl->cf_root = NULL; bl->input_pairs = NULL; bl->phis = NULL; - return bl; -} /* create_block */ + bl->meet_input = meet_input; -/** - * Adds a block to a partition. - * - * @param partition the partition to add to - * @param block the block to add - */ -static void add_block(partition_t *partition, block_t *block) { - list_add_tail(&block->block_list, &partition->blocks); + /* put it into the list of partition blocks */ + list_add_tail(&bl->block_list, &partition->blocks); ++partition->n_blocks; -} /* add_block */ + + /* put in into the list of all blocks */ + bl->all_next = env->all_blocks; + env->all_blocks = bl; + + return bl; +} /* create_block */ /** - * Allocate a new node. + * Allocate a new node and add it to a blocks wait queue. * * @param irn the IR-node + * @param block the block to add to * @param env the environment */ -static node_t *create_node(ir_node *irn, environment_t *env) { +static node_t *create_node(ir_node *irn, block_t *block, environment_t *env) { node_t *node = obstack_alloc(&env->obst, sizeof(*node)); node->node = irn; - node->next = NULL; node->is_input = 0; - return node; -} /* create_node */ -/** - * Adds a node to a block wait queue. - * - * @param block the block to add to - * @param node the node to add - */ -static void add_node(block_t *block, node_t *node) { list_add_tail(&node->node_list, &block->nodes); -} /* add_node */ + + return node; +} /* create_node */ /** * Add an input pair to a block. @@ -363,7 +391,7 @@ static opcode_key_t *opcode(const node_t *node, environment_t *env) { } key.mode = get_irn_mode(node->node); key.u.proj = 0; - key.u.ent = NULL; + key.u.addr = NULL; switch (key.code) { case iro_Proj: @@ -372,6 +400,18 @@ static opcode_key_t *opcode(const node_t *node, environment_t *env) { case iro_Sel: key.u.ent = get_Sel_entity(irn); break; + case iro_SymConst: + key.u.sym = get_SymConst_symbol(irn); + break; + case iro_Const: + key.u.tv = get_Const_tarval(irn); + break; + case iro_Conv: + key.u.intVal = get_Conv_strict(irn); + break; + case iro_Div: + key.u.intVal = is_Div_remainderless(irn); + break; default: break; } @@ -408,7 +448,7 @@ static partition_t *split(partition_t *Z, block_t *g, environment_t *env) { Z->n_blocks -= n; /* Move g to a new partition, Z'. */ - Z_prime = create_partition(env); + Z_prime = create_partition(Z->meet_block, env); for (block = g; block != NULL; block = block->next) { list_add_tail(&block->block_list, &Z_prime->blocks); } @@ -419,11 +459,25 @@ static partition_t *split(partition_t *Z, block_t *g, environment_t *env) { return Z_prime; } /* split */ +/** + * 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) { + /* for now, do NOT turn direct calls into indirect one */ + if (index != 1) + return 1; + if (! is_SymConst_addr_ent(pred)) + return 1; + if (! is_Call(irn)) + return 1; + return 0; +} /* is_input_node */ + /** * Propagate nodes on all wait queues of the given partition. * * @param part the partition - * @param env the environment + * @param env the environment */ void propagate_blocks(partition_t *part, environment_t *env) { block_t *ready_blocks = NULL; @@ -432,9 +486,9 @@ void propagate_blocks(partition_t *part, environment_t *env) { listmap_t map; listmap_entry_t *iter; - DB((dbg, LEVEL_2, "Propagate blocks on part%u\n", part->nr)); + DB((dbg, LEVEL_2, " Propagate blocks on part%u\n", part->nr)); - /* Let map be an empty mapping from the range of Opcodes to (local) list of Nodes. */ + /* Let map be an empty mapping from the range of Opcodes to (local) list of blocks. */ listmap_init(&map); list_for_each_entry_safe(block_t, bl, next, &part->blocks, block_list) { opcode_key_t *id; @@ -445,7 +499,7 @@ void propagate_blocks(partition_t *part, environment_t *env) { bl->next = ready_blocks; ready_blocks = bl; ++n_ready; - DB((dbg, LEVEL_1, "Block %+F completely processed\n", bl->block)); + DB((dbg, LEVEL_2, " Block %+F completely processed\n", bl->block)); continue; } @@ -458,7 +512,7 @@ void propagate_blocks(partition_t *part, environment_t *env) { ir_node *irn = node->node; int i; - DB((dbg, LEVEL_3, " propagate %+F\n", node->node)); + DB((dbg, LEVEL_3, " propagate %+F\n", irn)); ir_normalize_node(node->node); for (i = get_irn_arity(irn) - 1; i >= 0; --i) { ir_node *pred = get_irn_n(irn, i); @@ -466,15 +520,19 @@ void propagate_blocks(partition_t *part, environment_t *env) { node_t *p_node; if (block != bl->block) { - p_node = create_node(pred, env); - p_node->is_input = 1; - add_node(bl, p_node); - if (! is_Phi(irn)) - add_pair(bl, node->node, i, env); + p_node = create_node(pred, bl, env); + if (is_input_node(pred, irn, i)) { + /* is a block live input */ + p_node->is_input = 1; + if (! is_Phi(irn)) + add_pair(bl, irn, i, env); + } else if (is_Phi(pred)) { + /* update the Phi list */ + add_phi(bl, pred, env); + } } else if (! irn_visited_else_mark(pred)) { /* not yet visited, ok */ - p_node = create_node(pred, env); - add_node(bl, p_node); + p_node = create_node(pred, bl, env); if (is_Phi(pred)) { /* update the Phi list */ @@ -504,10 +562,10 @@ void propagate_blocks(partition_t *part, environment_t *env) { list_del(&Z->part_list); if (Z->n_blocks > 1) { - DB((dbg, LEVEL_1, "Partition %u is ready\n", Z->nr)); + DB((dbg, LEVEL_2, " Partition %u is ready\n", Z->nr)); list_add(&Z->part_list, &env->ready); } else { - DB((dbg, LEVEL_1, "Partition %u contains only one block, killed\n", Z->nr)); + DB((dbg, LEVEL_2, " Partition %u contains only one block, killed\n", Z->nr)); } } @@ -536,15 +594,98 @@ 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 == 1) { - /* only one block left, move to ready */ + if (part->n_blocks < 2) { + /* zero or one block left, kill this partition */ list_del(&part->part_list); - DB((dbg, LEVEL_1, "Partition %u contains only one block, killed\n", part->nr)); + DB((dbg, LEVEL_2, " Partition %u contains less than 2 blocks, killed\n", part->nr)); } else propagate_blocks(part, env); } } /* propagate */ +/** + * Map a block to the phi[block->input] live-trough. + */ +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 + is a live-out and not a live trough. + Live-outs are tested inside propagate, so map all of + them to the "general" value NULL */ + if (get_nodes_block(input) == bl->block) + return NULL; + return input; +} /* live_throughs */ + +/** + * Split partition by live-outs and live-troughs. + * + * @param part the partition + * @param env the environment + */ +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; + + DB((dbg, LEVEL_2, " Propagate live-troughs on part%u\n", part->nr)); + + for (phi = get_Block_phis(meet_block); phi != NULL; phi = get_Phi_next(phi)) { + /* propagate on all Phis of the meet-block */ + + if (part->n_blocks < 2) { + /* zero or one block left, kill this partition */ + list_del(&part->part_list); + DB((dbg, LEVEL_2, " Partition %u contains less than 2 blocks, killed\n", part->nr)); + return; + } + + /* Let map be an empty mapping from the range of live-troughs to (local) list of blocks. */ + listmap_init(&map); + list_for_each_entry_safe(block_t, bl, next, &part->blocks, block_list) { + opcode_key_t *id; + listmap_entry_t *entry; + + /* Add bl to map[live_trough(bl)]. */ + id = live_throughs(bl, phi); + entry = listmap_find(&map, id); + bl->next = entry->list; + entry->list = bl; + } + + /* for all sets S except one in the range of map do */ + for (iter = map.values; iter != NULL; iter = iter->next) { + block_t *S; + + if (iter->next == NULL) { + /* this is the last entry, ignore */ + break; + } + S = iter->list; + + /* Add SPLIT( X, S ) to P. */ + split(part, S, 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) { + 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 * by one representative. @@ -559,11 +700,11 @@ void propagate(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, *end_block; - ir_node **ins; + 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, n, block_nr; + int i, j, k, n, block_nr, n_phis; list_del(&repr->block_list); @@ -572,23 +713,29 @@ static void apply(ir_graph *irg, partition_t *part) { n = get_Block_n_cfgpreds(block); ins = NEW_ARR_F(ir_node *, n); - for (i = 0; i < n; ++i) + for (i = 0; i < n; ++i) { ins[i] = get_Block_cfgpred(block, i); + } /* ... for all existing Phis ... */ for (repr_phi = repr->phis; repr_phi != NULL; repr_phi = repr_phi->next) { repr_phi->ins = NEW_ARR_F(ir_node *, n); for (i = 0; i < n; ++i) - ins[i] = get_Phi_pred(repr_phi->phi, i); + repr_phi->ins[i] = get_Phi_pred(repr_phi->phi, i); } /* ... and all newly created Phis */ for (repr_pair = repr->input_pairs; repr_pair != NULL; repr_pair = repr_pair->next) { - repr_pair->ins = NEW_ARR_F(ir_node *, part->n_blocks); - repr_pair->ins[0] = get_irn_n(repr_pair->irn, repr_pair->index); + ir_node *input = get_irn_n(repr_pair->irn, repr_pair->index); + + repr_pair->ins = NEW_ARR_F(ir_node *, n); + for (i = 0; i < n; ++i) + repr_pair->ins[i] = input; } + DB((dbg, LEVEL_1, "Replacing ")); + /* collect new in arrays */ end = get_irg_end(irg); block_nr = 0; @@ -596,6 +743,8 @@ static void apply(ir_graph *irg, partition_t *part) { block = bl->block; ++block_nr; + DB((dbg, LEVEL_1, "%+F, ", block)); + /* first step: kill any keep-alive from this block */ for (i = get_End_n_keepalives(end) - 1; i >= 0; --i) { ir_node *ka = get_End_keepalive(end, i); @@ -612,28 +761,70 @@ static void apply(ir_graph *irg, partition_t *part) { /* second step: update control flow */ n = get_Block_n_cfgpreds(block); for (i = 0; i < n; ++i) { - ARR_APP1(ir_node *, ins, get_Block_cfgpred(block, i)); + ir_node *pred = get_Block_cfgpred(block, i); + ARR_APP1(ir_node *, ins, pred); } /* third step: update Phis */ for (repr_phi = repr->phis, phi = bl->phis; repr_phi != NULL; repr_phi = repr_phi->next, phi = phi->next) { - for (i = 0; i < n; ++i) - ARR_APP1(ir_node *, repr_phi->ins, get_Phi_pred(phi->phi, i)); + for (i = 0; i < n; ++i) { + ir_node *pred = get_Phi_pred(phi->phi, i); + ARR_APP1(ir_node *, repr_phi->ins, pred); + } } /* fourth step: update inputs for new Phis */ for (repr_pair = repr->input_pairs, pair = bl->input_pairs; repr_pair != NULL; repr_pair = repr_pair->next, pair = pair->next) { - repr_pair->ins[block_nr] = get_irn_n(pair->irn, pair->index); + ir_node *input = get_irn_n(pair->irn, pair->index); + + for (i = 0; i < n; ++i) + ARR_APP1(ir_node *, repr_pair->ins, input); } } + DB((dbg, LEVEL_1, "by %+F\n", repr->block)); /* rewire block input ... */ n = ARR_LEN(ins); + + /* + * Some problem here. For: + * if (x) y = 1; else y = 2; + * + * the following code is constructed: + * + * b0: if (x) goto b1; else goto b1; + * b1: y = Phi(1,2) + * + * However, both predecessors of b1 are b0, making the Phi + * "wrong". + * + * We solve this by fixing critical edges. + */ + for (i = 0; i < n; ++i) { + ir_node *pred = ins[i]; + const ir_op *cfop; + + if (is_Bad(pred)) + continue; + + cfop = get_irn_op(skip_Proj(pred)); + if (is_op_fragile(cfop)) { + /* ignore exception flow */ + continue; + } + 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); + ins[i] = jmp; + } + } + block = repr->block; set_irn_in(block, n, ins); DEL_ARR_F(ins); @@ -645,7 +836,6 @@ static void apply(ir_graph *irg, partition_t *part) { } /* ... and all inputs by creating new Phis ... */ - n = part->n_blocks; 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); @@ -653,69 +843,95 @@ static void apply(ir_graph *irg, partition_t *part) { set_irn_n(repr_pair->irn, repr_pair->index, phi); DEL_ARR_F(repr_pair->ins); + + /* might be optimized away */ + if (is_Phi(phi)) + add_Block_phi(block, phi); } - /* ... finally rewire the end block */ - end_block = get_irg_end_block(irg); - n = get_Block_n_cfgpreds(end_block); + /* ... finally rewire the meet block and fix its Phi-nodes */ + meet_block = part->meet_block; + n = get_Block_n_cfgpreds(meet_block); ins = NEW_ARR_F(ir_node *, n); + n_phis = 0; + for (p = get_Block_phis(meet_block); p != NULL; p = get_Phi_next(p)) { + ++n_phis; + } + + phi_ins = NEW_ARR_F(ir_node *, n_phis * n); + for (i = j = 0; i < n; ++i) { - ir_node *out = get_Block_cfgpred(end_block, i); + ir_node *pred = get_Block_cfgpred(meet_block, i); list_for_each_entry(block_t, bl, &part->blocks, block_list) { - node_t *root; + if (bl->cf_root->node == pred) + goto continue_outer; + } + ins[j] = pred; - for (root = bl->roots; root != NULL; root = root->next) { - if (root->node == out) - goto found; - } + for (k = 0, p = get_Block_phis(meet_block); p != NULL; p = get_Phi_next(p), ++k) { + phi_ins[k * n + j] = get_Phi_pred(p, i); } - ins[j++] = out; -found: - ; + ++j; + +continue_outer: + ; } - set_irn_in(end_block, j, ins); - DEL_ARR_F(ins); - /* control flow changed */ - set_irg_outs_inconsistent(irg); - set_irg_extblk_inconsistent(irg); - set_irg_doms_inconsistent(irg); - /* Hmm, only the root loop is inconsistent */ - set_irg_loopinfo_inconsistent(irg); -} /* apply */ + /* fix phis */ + if (j == 1) { + for (k = 0, p = get_Block_phis(meet_block); p != NULL; p = next, ++k) { + next = get_Phi_next(p); -/* Combines congruent end blocks into one. */ -int melt_end_blocks(ir_graph *irg) { - ir_graph *rem; - ir_node *end; - environment_t env; - partition_t *part; - int i, res; + exchange(p, phi_ins[k * n]); + } + /* all Phis killed */ + set_Block_phis(meet_block, NULL); + } else { + for (k = 0, p = get_Block_phis(meet_block); p != NULL; p = next, ++k) { + next = get_Phi_next(p); - rem = current_ir_graph; - current_ir_graph = irg; + set_irn_in(p, j, &phi_ins[k * n]); + } + } + DEL_ARR_F(phi_ins); - /* register a debug mask */ - FIRM_DBG_REGISTER(dbg, "firm.opt.blocks"); + /* fix inputs of the meet block */ + set_irn_in(meet_block, j, ins); + DEL_ARR_F(ins); +} /* apply */ - DEBUG_ONLY(part_nr = 0); - DB((dbg, LEVEL_1, "Melting end blocks for %+F\n", irg)); +/** + * Create a partition for a the end block. + * + * @param end_block the end block + * @param env the environment + */ +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; - ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED); - inc_irg_visited(irg); + /* collect normal blocks */ + for (i = get_Block_n_cfgpreds(end_block) - 1; i >= 0; --i) { + ir_node *pred = get_Block_cfgpred(end_block, i); + ir_node *block; + block_t *bl; + node_t *node; - obstack_init(&env.obst); - INIT_LIST_HEAD(&env.partitions); - INIT_LIST_HEAD(&env.ready); - env.opcode2id_map = new_set(cmp_opcode, iro_Last * 4); + mark_irn_visited(pred); + + block = get_nodes_block(pred); + bl = create_block(block, i, part, env); + node = create_node(pred, bl, env); - part = create_partition(&env); + bl->cf_root = node; + } /* collect all no-return blocks */ - end = get_irg_end(irg); + end = get_irg_end(current_ir_graph); for (i = get_End_n_keepalives(end) - 1; i >= 0; --i) { ir_node *ka = get_End_keepalive(end, i); ir_node *block; @@ -728,19 +944,30 @@ int melt_end_blocks(ir_graph *irg) { /* found one */ block = get_nodes_block(ka); - bl = create_block(block, &env); - add_block(part, bl); - node = create_node(ka, &env); - add_node(bl, node); + bl = create_block(block, -1, part, env); + node = create_node(ka, bl, env); - node->next = bl->roots; - bl->roots = node; + bl->cf_root = node; } - /* collect normal blocks */ - end = get_irg_end_block(irg); - for (i = get_Block_n_cfgpreds(end) - 1; i >= 0; --i) { - ir_node *pred = get_Block_cfgpred(end, i); + dump_partition("Created", part); +} /* partition_for_end_block */ + +#ifdef GENERAL_SHAPE +/** + * Create a partition for a given meet block. + * + * @param block the meet block + * @param preds array of candidate predecessors + * @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) { + partition_t *part = create_partition(block, env); + int i; + + for (i = n_preds - 1; i >= 0; --i) { + ir_node *pred = preds[i].pred; ir_node *block; block_t *bl; node_t *node; @@ -748,28 +975,275 @@ int melt_end_blocks(ir_graph *irg) { mark_irn_visited(pred); block = get_nodes_block(pred); - bl = create_block(block, &env); - add_block(part, bl); - node = create_node(pred, &env); - add_node(bl, node); + bl = create_block(block, preds[i].index, part, env); + node = create_node(pred, bl, env); + + bl->cf_root = node; + } + + dump_partition("Created", part); +} /* partition_for_block */ + +/** + * Walker: clear the links of all block phi lists and normal + * links. + */ +static void clear_phi_links(ir_node *irn, void *env) { + (void) env; + if (is_Block(irn)) { + 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; + ir_node **live_outs = env->live_outs; + ir_node *this_block; + int i; + + if (is_Block(irn)) + return; + + /* ignore Keep-alives */ + if (is_End(irn)) + return; + + this_block = get_nodes_block(irn); + + if (is_Phi(irn)) { + /* update the Phi list */ + add_Block_phi(this_block, irn); + } + + for (i = get_irn_arity(irn) - 1; i >= 0; --i) { + ir_node *pred_block; + ir_node *pred = get_irn_n(irn, i); + int idx = get_irn_idx(pred); + + if (live_outs[idx] != NULL) { + /* already marked as live-out */ + return; + } + + pred_block = get_nodes_block(pred); + /* Phi nodes always refer to live-outs */ + if (is_Phi(irn) || this_block != pred_block) { + /* pred is a live-out */ + live_outs[idx] = pred_block; + } + } +} /* find_liveouts */ + +/** + * Check if the current block is the meet block of a its predecessors. + */ +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)) { + /* always create a partition for the end block */ + partition_for_end_block(block, env); + return; + } + + n = get_Block_n_cfgpreds(block); + if (n <= 1) { + /* Must have at least two predecessors */ + return; + } + + NEW_ARR_A(pred_t, preds, n); + 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)); - node->next = bl->roots; - bl->roots = node; + preds[k].pred = pred; + preds[k].index = i; } + 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) { + ir_node *const *pa = a; + 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); + ir_opcode code_b = get_irn_opcode(irn_b); + ir_mode *mode_a, *mode_b; + unsigned idx_a, idx_b; + + /* try opcode first */ + if (code_a != code_b) + return code_a - code_b; + + /* try mode */ + mode_a = get_irn_mode(irn_a); + mode_b = get_irn_mode(irn_b); + + if (mode_a != mode_b) + return mode_a < mode_b ? -1 : +1; + + /* last resort: index */ + idx_a = get_irn_idx(irn_a); + idx_b = get_irn_idx(irn_b); + + return (idx_a > idx_b) - (idx_a < idx_b); +} /* cmp_nodes */ + +/** + * Add the roots to all blocks. + */ +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; + + for (idx = 0; idx < n; ++idx) { + ir_node *block = live_outs[idx]; + + if (block != NULL && is_Block(block)) { + block_t *bl = get_Block_entry(block); + + if (bl != NULL) { + ir_node *irn = get_idx_irn(irg, idx); + + if (!irn_visited_else_mark(irn)) { + ARR_APP1(ir_node *, bl->roots, irn); + } + } + } + } + /* + * Now sort the roots to normalize them as good as possible. + * 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); + +#if 1 + /* TODO: is this really needed? The roots are already in + idx-order by construction, which might be good enough. */ + qsort(bl->roots, n, sizeof(bl->roots[0]), cmp_nodes); +#endif + + DB((dbg, LEVEL_2, " Adding Roots for block %+F\n ", bl->block)); + /* ok, add them sorted */ + for (i = 0; i < n; ++i) { + DB((dbg, LEVEL_2, "%+F, ", bl->roots[i])); + create_node(bl->roots[i], bl, env); + } + DB((dbg, LEVEL_2, "\n")); + 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) { + ir_graph *rem; + environment_t env; + partition_t *part; + 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); + DB((dbg, LEVEL_1, "Shaping blocks for %+F\n", irg)); + + /* works better, when returns are placed at the end of the blocks */ + normalize_n_returns(irg); + + obstack_init(&env.obst); + INIT_LIST_HEAD(&env.partitions); + INIT_LIST_HEAD(&env.ready); + 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.all_blocks = NULL; + + ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK | IR_RESOURCE_PHI_LIST); + +#ifdef GENERAL_SHAPE + /* + * Detect, which nodes are live-out only: these are the roots of our blocks. + * Build phi lists. + */ + irg_walk_graph(irg, clear_phi_links, find_liveouts, &env); +#endif + + ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED); + + inc_irg_visited(irg); +#ifdef GENERAL_SHAPE + /* + * Detect all control flow meets and create partitions. + */ + irg_block_walk_graph(irg, NULL, check_for_cf_meet, &env); + + /* add root nodes to the partition blocks */ + add_roots(irg, &env); +#else + partition_for_end_block(get_irg_end_block(irg), &env); +#endif + + propagate_live_troughs(&env); while (! list_empty(&env.partitions)) propagate(&env); res = !list_empty(&env.ready); + //if (res) dump_ir_block_graph(irg, "-before"); + list_for_each_entry(partition_t, part, &env.ready, part_list) { dump_partition("Ready Partition", part); apply(irg, part); } - ir_free_resources(irg, IR_RESOURCE_IRN_VISITED); + ir_free_resources(irg, IR_RESOURCE_IRN_VISITED | IR_RESOURCE_IRN_LINK | IR_RESOURCE_PHI_LIST); + + 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"); + } + + DEL_ARR_F(env.live_outs); del_set(env.opcode2id_map); obstack_free(&env.obst, NULL); current_ir_graph = rem; return res; -} /* melt_end_blocks */ +} /* shape_blocks */