-#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 <string.h>
#endif
+#include "debug.h"
#include "interval_analysis.h"
-
+#include "execution_frequency.h"
#include "firm_common_t.h"
#include "set.h"
#include "array.h"
#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. */
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;
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) {
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) {
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);
}
/*------------------------------------------------------------------*/
/* 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) {
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;
}
-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:
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);
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 */
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");
}
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);
}
}
}
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);
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))));
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))));
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;
}
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);
}
projects / libfirm / blobdiff