X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fopt%2Fopt_blocks.c;h=4ad1b952ef16821794efb31221f0714be6acb724;hb=1a4bb21b7aa32f0bcd282d4c1cdb144aca601fa9;hp=61d898047258f3858bb37330e515bb1b4104a536;hpb=76c005588cd5c7c5f41e0b38f61c2ee54d9faa51;p=libfirm diff --git a/ir/opt/opt_blocks.c b/ir/opt/opt_blocks.c index 61d898047..4ad1b952e 100644 --- a/ir/opt/opt_blocks.c +++ b/ir/opt/opt_blocks.c @@ -40,6 +40,9 @@ #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; @@ -48,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 { @@ -55,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; }; @@ -81,7 +89,8 @@ struct block_t { 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 craeted blocks. */ + block_t *all_next; /**< Links all created blocks. */ + int meet_input; /**< Input number of this block in the meet-block. */ }; /** A node. */ @@ -116,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. */ @@ -236,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 */ /** @@ -249,7 +265,7 @@ 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 */ /** @@ -274,10 +290,11 @@ static partition_t *create_partition(ir_node *meet_block, environment_t *env) { * Allocate a new block in the given partition. * * @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, partition_t *partition, 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); @@ -289,6 +306,7 @@ static block_t *create_block(ir_node *block, partition_t *partition, environment bl->cf_root = NULL; bl->input_pairs = NULL; bl->phis = NULL; + bl->meet_input = meet_input; /* put it into the list of partition blocks */ list_add_tail(&bl->block_list, &partition->blocks); @@ -373,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: @@ -382,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; } @@ -429,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; @@ -444,7 +488,7 @@ void propagate_blocks(partition_t *part, environment_t *env) { 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; @@ -477,11 +521,14 @@ void propagate_blocks(partition_t *part, environment_t *env) { if (block != bl->block) { p_node = create_node(pred, bl, env); - /* do not threat Constants like live-ins */ - if (! is_irn_constlike(pred)) { + 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 */ @@ -556,6 +603,89 @@ void propagate(environment_t *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. @@ -766,43 +896,13 @@ continue_outer: set_irn_in(p, j, &phi_ins[k * n]); } } + DEL_ARR_F(phi_ins); /* fix inputs of the meet block */ set_irn_in(meet_block, j, ins); DEL_ARR_F(ins); } /* apply */ -/** - * 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, ir_node *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]; - ir_node *block; - block_t *bl; - node_t *node; - - mark_irn_visited(pred); - - block = get_nodes_block(pred); - bl = create_block(block, part, env); - node = create_node(pred, bl, env); - - bl->cf_root = node; - } - - dump_partition("Created", part); -} /* partition_for_block */ - - /** * Create a partition for a the end block. * @@ -824,7 +924,7 @@ static void partition_for_end_block(ir_node *end_block, environment_t *env) { mark_irn_visited(pred); block = get_nodes_block(pred); - bl = create_block(block, part, env); + bl = create_block(block, i, part, env); node = create_node(pred, bl, env); bl->cf_root = node; @@ -844,7 +944,7 @@ static void partition_for_end_block(ir_node *end_block, environment_t *env) { /* found one */ block = get_nodes_block(ka); - bl = create_block(block, part, env); + bl = create_block(block, -1, part, env); node = create_node(ka, bl, env); bl->cf_root = node; @@ -853,11 +953,43 @@ static void partition_for_end_block(ir_node *end_block, environment_t *env) { 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; + + mark_irn_visited(pred); + + block = get_nodes_block(pred); + 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); @@ -865,7 +997,7 @@ static void clear_phi_links(ir_node *irn, void *env) { } /* clear_phi_links */ /** - * Walker, detect live-out only nodes. + * Walker, detect live-out nodes. */ static void find_liveouts(ir_node *irn, void *ctx) { environment_t *env = ctx; @@ -892,21 +1024,19 @@ static void find_liveouts(ir_node *irn, void *ctx) { ir_node *pred = get_irn_n(irn, i); int idx = get_irn_idx(pred); - if (live_outs[idx] == pred) { - /* referenced by other nodes inside this block */ + if (live_outs[idx] != NULL) { + /* already marked as live-out */ return; } pred_block = get_nodes_block(pred); - if (this_block != pred_block) { + /* 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; - } else { - /* this node is referenced from inside this block */ - live_outs[idx] = pred; } } -} +} /* find_liveouts */ /** * Check if the current block is the meet block of a its predecessors. @@ -914,7 +1044,7 @@ static void find_liveouts(ir_node *irn, void *ctx) { static void check_for_cf_meet(ir_node *block, void *ctx) { environment_t *env = ctx; int i, k, n; - ir_node **preds; + pred_t *preds; if (block == get_irg_end_block(current_ir_graph)) { /* always create a partition for the end block */ @@ -927,16 +1057,21 @@ static void check_for_cf_meet(ir_node *block, void *ctx) { /* Must have at least two predecessors */ return; } - NEW_ARR_A(ir_node *, preds, n); + 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)) + if (! is_Jmp(pred) && ! is_Raise(pred) && !is_Bad(pred)) continue; - preds[k++] = pred; + + pred_block = get_nodes_block(skip_Proj(pred)); + + preds[k].pred = pred; + preds[k].index = i; } if (k > 1) @@ -947,12 +1082,14 @@ 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) { - const ir_node *irn_a = a; - const ir_node *irn_b = b; - 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; + 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) @@ -1019,6 +1156,7 @@ static void add_roots(ir_graph *irg, environment_t *env) { bl->roots = NULL; } } /* add_roots */ +#endif /* GENERAL_SHAPE */ /* Combines congruent end blocks into one. */ int shape_blocks(ir_graph *irg) { @@ -1032,7 +1170,6 @@ int shape_blocks(ir_graph *irg) { /* register a debug mask */ FIRM_DBG_REGISTER(dbg, "firm.opt.blocks"); - firm_dbg_set_mask(dbg, 7); DEBUG_ONLY(part_nr = 0); DB((dbg, LEVEL_1, "Shaping blocks for %+F\n", irg)); @@ -1053,15 +1190,18 @@ int shape_blocks(ir_graph *irg) { 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. */ @@ -1069,11 +1209,17 @@ int shape_blocks(ir_graph *irg) { /* 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); @@ -1086,13 +1232,15 @@ int shape_blocks(ir_graph *irg) { 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); /* 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;