X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fana%2Finterval_analysis.c;h=b0bc7deb7e75be121b49b05f46066efd3ce975a5;hb=ee7cb73523122ef2cda446d9cbc675edb89acabe;hp=96b4e9443ec82dec19b4f5953dfe75ce986928d8;hpb=100c7bfcbf4e395d5d4e560a3dd563440aa7096d;p=libfirm diff --git a/ir/ana/interval_analysis.c b/ir/ana/interval_analysis.c index 96b4e9443..b0bc7deb7 100644 --- a/ir/ana/interval_analysis.c +++ b/ir/ana/interval_analysis.c @@ -1,13 +1,36 @@ -#ifdef HAVE_CONFIG_H +/* + * 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. + */ + +/** + * @file + * @brief Implementation of interval analysis + * @version $Id$ + */ #include "config.h" -#endif #ifdef HAVE_STRING_H #include #endif +#include "debug.h" #include "interval_analysis.h" - +#include "execution_frequency.h" #include "firm_common_t.h" #include "set.h" #include "array.h" @@ -17,6 +40,10 @@ #include "irdump_t.h" #include "irdom.h" #include "irflag.h" +#include "irprintf.h" +#include "hashptr.h" + +DEBUG_ONLY(static firm_dbg_module_t *dbg); /*------------------------------------------------------------------*/ /* A new in array via a hashmap. */ @@ -37,15 +64,15 @@ static set *region_attr_set = NULL; int region_attr_cmp(const void *e1, const void *e2, size_t size) { region_attr *ra1 = (region_attr *)e1; region_attr *ra2 = (region_attr *)e2; + (void) size; return (ra1->reg != ra2->reg); } -static INLINE int attr_set_hash (region_attr *a) { - unsigned int v = (unsigned int) a->reg; - return v ^ (v>>8); +static inline int attr_set_hash(region_attr *a) { + return HASH_PTR(a->reg); } -static INLINE region_attr *get_region_attr(void *region) { +static inline region_attr *get_region_attr(void *region) { region_attr r_attr, *res; r_attr.reg = region; @@ -71,7 +98,7 @@ int get_region_n_ins(void *region) { void *get_region_in(void *region, int pos) { assert(0 <= pos && pos < get_region_n_ins(region)); - return (get_region_attr(region)->in_array)[pos]; + return ((get_region_attr(region)->in_array)[pos]); } void add_region_in (void *region, void *in) { @@ -93,7 +120,7 @@ void inc_region_n_exc_outs(void *region) { void *get_loop_cfop(void *region, int pos) { assert(0 <= pos && pos < get_region_n_ins(region)); - return (get_region_attr(region)->op_array)[pos]; + return ((get_region_attr(region)->op_array)[pos]); } void add_loop_cfop (void *region, void *cfop) { @@ -101,8 +128,9 @@ void add_loop_cfop (void *region, void *cfop) { ARR_APP1(void *, get_region_attr(region)->op_array, cfop); } -static INLINE void exc_outs(void *reg, ir_node *cfop) { - if (is_fragile_op(cfop)) inc_region_n_exc_outs(reg); +static inline void exc_outs(void *reg, ir_node *cfop) { + if (is_fragile_op(cfop) || (is_fragile_Proj(cfop))) + inc_region_n_exc_outs(reg); } /*------------------------------------------------------------------*/ @@ -110,15 +138,15 @@ static INLINE void exc_outs(void *reg, ir_node *cfop) { /* Walk a loop and add all edges. Walk inner loops by recursion. */ /*------------------------------------------------------------------*/ -/* return true if outer can be reached from inner via the outer loop relation */ +/* return non-zero if outer can be reached from inner via the outer loop relation */ static int find_outer_loop(ir_loop *inner, ir_loop *outer, ir_node *b, ir_node *cfop) { if (get_loop_outer_loop(inner) == outer) { add_region_in(inner, b); add_loop_cfop(inner, cfop); exc_outs(b, cfop); - return true; + return 1; } - return false; + return 0; } static int test_loop_nest(ir_node *pred_b, ir_loop *nest) { @@ -128,34 +156,34 @@ static int test_loop_nest(ir_node *pred_b, ir_loop *nest) { loop_element e = get_loop_element(nest, i); switch (*e.kind) { case k_ir_node: { - if (e.node == pred_b) return true; + if (e.node == pred_b) return 1; } break; case k_ir_loop: { - if (test_loop_nest(pred_b, e.son)) return true; + if (test_loop_nest(pred_b, e.son)) return 1; } break; default: break; } } - return false; + return 0; } static int find_inner_loop(ir_node *b, ir_loop *l, ir_node *pred, ir_node *cfop) { int i, n_elems = get_loop_n_elements(l); - int found = false; + int found = 0; for (i = 0; (i < n_elems) && !found; ++i) { loop_element e = get_loop_element(l, i); switch (*e.kind) { case k_ir_node: { - if (e.node == b) return false; + if (e.node == b) return 0; } break; case k_ir_loop: { found = test_loop_nest(pred, e.son); if (found) { - add_region_in(b, e.son); - exc_outs(e.son, cfop); - //if (is_fragile_op(cfop)) inc_region_n_exc_outs(b); - return found; + add_region_in(b, e.son); + exc_outs(e.son, cfop); + //if (is_fragile_op(cfop)) inc_region_n_exc_outs(b); + return found; } } break; default: break; @@ -165,42 +193,38 @@ static int find_inner_loop(ir_node *b, ir_loop *l, ir_node *pred, ir_node *cfop) } -static int find_previous_loop(ir_loop *l, ir_loop *pred_l, ir_node *b, ir_node *pred_b, ir_node *cfop) { +static int find_previous_loop(ir_loop *l, ir_loop *pred_l, ir_node *b, + ir_node *pred_b, ir_node *cfop) +{ ir_loop *outer = get_loop_outer_loop(l); int found, i; int l_pos = get_loop_element_pos(outer, l); + (void) pred_l; assert(l_pos > -1); assert(l_pos > 0 && "Is this a necessary condition? There could be a perfect nest ..."); - for (i = l_pos -1, found = false; i > -1 && !found; --i) { + for (i = l_pos -1, found = 0; i > -1 && !found; --i) { ir_loop *k = get_loop_element(outer, i).son; if (is_ir_loop(k)) { found = test_loop_nest(pred_b, k); if (found) { - add_region_in(l, k); - //if (is_fragile_op(cfop)) inc_region_n_exc_outs(k); - exc_outs(k, cfop); - add_loop_cfop(l, cfop); - add_region_in(b, NULL); + add_region_in(l, k); + //if (is_fragile_op(cfop)) inc_region_n_exc_outs(k); + exc_outs(k, cfop); + add_loop_cfop(l, cfop); + add_region_in(b, NULL); } } } - if (!found) { - DDMG(current_ir_graph); - DDML(l); - DDML(pred_l); - DDMN(b); - DDMN(pred_b); - } - return found; } -/* Compute the edges for the interval graph. +/** + * Compute the edges for the interval graph. * - * @param b The block for which to constuct the edges. + * @param b The block for which to construct the edges. * @param l The loop of b. * * There are four cases: @@ -226,20 +250,25 @@ static void construct_interval_block(ir_node *b, ir_loop *l) { if (is_backedge(b, i)) { if (b != get_loop_element(l, 0).node) { - if (get_firm_verbosity()) { - printf("Loophead not at loop position 0. "); DDMN(b); - } + DB((dbg, LEVEL_1, "Loophead not at loop position 0. %+F\n", b)); } /* There are no backedges in the interval decomposition. */ add_region_in(b, NULL); continue; } - cfop = skip_Proj(get_Block_cfgpred(b, i)); - pred = get_nodes_block(cfop); + cfop = get_Block_cfgpred(b, i); + if (is_Proj(cfop)) { + if (!is_Cond(get_Proj_pred(cfop))) { + cfop = skip_Proj(cfop); + } else { + assert(get_nodes_block(cfop) == get_nodes_block(skip_Proj(cfop))); + } + } + + pred = skip_Proj(get_nodes_block(cfop)); /* We want nice blocks. */ - assert( get_irn_op(pred) != op_Bad - && get_irn_op(skip_Proj(get_Block_cfgpred(b, i))) != op_Bad); + assert(!is_Bad(pred) && !is_Bad(skip_Proj(get_Block_cfgpred(b, i)))); pred_l = get_irn_loop(pred); if (pred_l == l) { add_region_in(b, pred); @@ -249,9 +278,7 @@ static void construct_interval_block(ir_node *b, ir_loop *l) { int found = find_inner_loop(b, l, pred, cfop); if (!found) { if (b != get_loop_element(l, 0).node) { - if (get_firm_verbosity()) { - printf("Loop entry not at loop position 0. "); DDMN(b); - } + DB((dbg, LEVEL_1, "Loop entry not at loop position 0. %+F\n", b)); } found = find_outer_loop(l, pred_l, pred, cfop); if (found) add_region_in(b, NULL); /* placeholder */ @@ -260,9 +287,6 @@ static void construct_interval_block(ir_node *b, ir_loop *l) { found = find_previous_loop(l, pred_l, b, pred, cfop); } if (!found) { - DDMG(current_ir_graph); - DDMN(b); - DDMN(pred); assert(is_backedge(b, i)); assert(found && "backedge from inner loop"); } @@ -271,10 +295,7 @@ static void construct_interval_block(ir_node *b, ir_loop *l) { if (b != get_loop_element(l, 0).node) { /* Check for improper region */ if (has_backedges(b)) { - printf("Improper Region!!!!!!\n"); - DDMG(current_ir_graph); - DDMN(b); - DDML(l); + ir_fprintf(stderr, "Improper Region!!!!!! %+F\n", b); } } } @@ -301,12 +322,13 @@ void construct_intervals(ir_graph *irg) { ir_graph *rem = current_ir_graph; current_ir_graph = irg; + FIRM_DBG_REGISTER(dbg, "firm.ana.interval"); + if (!region_attr_set) region_attr_set = new_set(region_attr_cmp, 256); construct_cf_backedges(current_ir_graph); - l = get_irg_loop(current_ir_graph); construct_interval_edges(l); @@ -339,9 +361,9 @@ void dump_region_edges(FILE *F, void *reg) { if (is_ir_node(reg) && get_Block_n_cfgpreds((ir_node *)reg) > get_region_n_ins(reg)) { for (i = n_ins; i < get_Block_n_cfgpreds((ir_node *)reg); ++i) { if (is_backedge((ir_node *)reg, i)) - fprintf (F, "backedge: { sourcename: \""); + fprintf (F, "backedge: { sourcename: \""); else - fprintf (F, "edge: { sourcename: \""); + fprintf (F, "edge: { sourcename: \""); PRINT_NODEID(((ir_node *)reg)); fprintf (F, "\" targetname: \""); PRINT_NODEID(get_nodes_block(skip_Proj(get_Block_cfgpred((ir_node *)reg, i)))); @@ -354,17 +376,16 @@ void dump_region_edges(FILE *F, void *reg) { if (is_ir_node(reg)) { if (get_Block_n_cfgpreds((ir_node *)reg) != get_region_n_ins(reg)) { - printf("n_cfgpreds = %d, n_ins = %d\n", get_Block_n_cfgpreds((ir_node *)reg), get_region_n_ins(reg)); - DDMN((ir_node *)reg); + ir_printf("n_cfgpreds = %d, n_ins = %d\n %+F\n", get_Block_n_cfgpreds((ir_node *)reg), get_region_n_ins(reg), (ir_node*) reg); } } if ((!target || (is_ir_node(reg) && !is_ir_node(target))) && i < get_Block_n_cfgpreds((ir_node *)reg)) { assert(is_ir_node(reg)); if (is_backedge((ir_node *)reg, i)) - fprintf (F, "backedge: { sourcename: \""); + fprintf (F, "backedge: { sourcename: \""); else - fprintf (F, "edge: { sourcename: \""); + fprintf (F, "edge: { sourcename: \""); PRINT_NODEID(((ir_node *)reg)); fprintf (F, "\" targetname: \""); PRINT_NODEID(get_nodes_block(skip_Proj(get_Block_cfgpred((ir_node *)reg, i)))); @@ -420,7 +441,7 @@ void dump_interval_block(FILE *F, ir_node *block) { ir_node *pred = get_Block_cfgpred(block, i); if (is_Bad(pred)) { if (! fl) - fprintf(F, "Bad pred at pos: "); + fprintf(F, "Bad pred at pos: "); fprintf(F, "%d ", i); fl = 1; } @@ -471,15 +492,16 @@ void dump_interval_loop(FILE *F, ir_loop *l) { void dump_interval_graph(ir_graph *irg, const char *suffix) { FILE *f; - if (strncmp(get_entity_name(get_irg_entity(irg)), dump_file_filter, strlen(dump_file_filter)) != 0) + if (!is_filtered_dump_name(get_entity_ident(get_irg_entity(irg)))) return; f = vcg_open(irg, suffix, "-intervals"); - dump_vcg_header(f, get_irg_dump_name(irg), NULL); + dump_vcg_header(f, get_irg_dump_name(irg), NULL, NULL); current_ir_graph = irg; dump_interval_loop(f, get_irg_loop(current_ir_graph)); - vcg_close(f); + dump_vcg_footer(f); + fclose(f); }