X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fana%2Fcallgraph.c;h=813fb253b0919bf91b9d6d9d51be82d0d12938e0;hb=cdcd17c48e951c6e0201c58b94aaf52a8769703c;hp=ffef4d059f15a17c23b6d8e3417e9dbb9b9b9cc9;hpb=9bf5225a473ec8b8d0d9f9ea4e49bd5cf5c8a4e1;p=libfirm diff --git a/ir/ana/callgraph.c b/ir/ana/callgraph.c index ffef4d059..813fb253b 100644 --- a/ir/ana/callgraph.c +++ b/ir/ana/callgraph.c @@ -1,5 +1,5 @@ /* - * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved. + * Copyright (C) 1995-2011 University of Karlsruhe. All right reserved. * * This file is part of libFirm. * @@ -22,18 +22,11 @@ * @brief Representation and computation of the callgraph. * @author Goetz Lindenmaier * @date 21.7.2004 - * @version $Id$ */ -#ifdef HAVE_CONFIG_H -# include "config.h" -#endif - -#ifdef HAVE_STRING_H -# include -#endif -# ifdef HAVE_STDLIB_H +#include "config.h" + +#include #include -#endif #include "callgraph.h" @@ -43,7 +36,6 @@ #include "irnode_t.h" #include "cgana.h" -#include "execution_frequency.h" #include "array.h" #include "pmap.h" @@ -52,43 +44,42 @@ #include "irgwalk.h" -static int master_cg_visited = 0; -static INLINE int cg_irg_visited (ir_graph *n); -static INLINE void mark_cg_irg_visited(ir_graph *n); -static INLINE void set_cg_irg_visited (ir_graph *n, int i); +static ir_visited_t master_cg_visited = 0; +static inline int cg_irg_visited (ir_graph *n); +static inline void mark_cg_irg_visited(ir_graph *n); -/** Returns the callgraph state of the program representation. */ -irp_callgraph_state get_irp_callgraph_state(void) { +irp_callgraph_state get_irp_callgraph_state(void) +{ return irp->callgraph_state; } -/* Sets the callgraph state of the program representation. */ -void set_irp_callgraph_state(irp_callgraph_state s) { +void set_irp_callgraph_state(irp_callgraph_state s) +{ irp->callgraph_state = s; } -/* Returns the number of procedures that call the given irg. */ -int get_irg_n_callers(ir_graph *irg) { - if (irg->callers) return ARR_LEN(irg->callers); - return -1; +size_t get_irg_n_callers(const ir_graph *irg) +{ + assert(irg->callers); + return irg->callers ? ARR_LEN(irg->callers) : 0; } -/* Returns the caller at position pos. */ -ir_graph *get_irg_caller(ir_graph *irg, int pos) { - assert(pos >= 0 && pos < get_irg_n_callers(irg)); - if (irg->callers) return irg->callers[pos]; - return NULL; +ir_graph *get_irg_caller(const ir_graph *irg, size_t pos) +{ + assert(pos < get_irg_n_callers(irg)); + return irg->callers ? irg->callers[pos] : NULL; } -/* Returns non-zero if the caller at position pos is "a backedge", i.e. a recursion. */ -int is_irg_caller_backedge(ir_graph *irg, int pos) { - assert(pos >= 0 && pos < get_irg_n_callers(irg)); +int is_irg_caller_backedge(const ir_graph *irg, size_t pos) +{ + assert(pos < get_irg_n_callers(irg)); return irg->caller_isbe != NULL ? rbitset_is_set(irg->caller_isbe, pos) : 0; } -/** Search the caller in the list of all callers and set it's backedge property. */ -static void set_irg_caller_backedge(ir_graph *irg, ir_graph *caller) { - int i, n_callers = get_irg_n_callers(irg); +/** Search the caller in the list of all callers and set its backedge property. */ +static void set_irg_caller_backedge(ir_graph *irg, const ir_graph *caller) +{ + size_t i, n_callers = get_irg_n_callers(irg); /* allocate a new array on demand */ if (irg->caller_isbe == NULL) @@ -101,9 +92,9 @@ static void set_irg_caller_backedge(ir_graph *irg, ir_graph *caller) { } } -/* Returns non-zero if the irg has a backedge caller. */ -int has_irg_caller_backedge(ir_graph *irg) { - int i, n_callers = get_irg_n_callers(irg); +int has_irg_caller_backedge(const ir_graph *irg) +{ + size_t i, n_callers = get_irg_n_callers(irg); if (irg->caller_isbe != NULL) { for (i = 0; i < n_callers; ++i) @@ -118,54 +109,51 @@ int has_irg_caller_backedge(ir_graph *irg) { * Given the position pos_caller of an caller of irg, return * irg's callee position on that caller. */ -static int reverse_pos(ir_graph *callee, int pos_caller) { +static size_t reverse_pos(const ir_graph *callee, size_t pos_caller) +{ ir_graph *caller = get_irg_caller(callee, pos_caller); /* search the other relation for the corresponding edge. */ - int pos_callee = -1; - int i, n_callees = get_irg_n_callees(caller); + size_t i, n_callees = get_irg_n_callees(caller); for (i = 0; i < n_callees; ++i) { if (get_irg_callee(caller, i) == callee) { - pos_callee = i; - break; + return i; } } - assert(pos_callee >= 0); + assert(!"reverse_pos() did not find position"); - return pos_callee; + return 0; } -/* Returns the maximal loop depth of call nodes that call along this edge. */ -int get_irg_caller_loop_depth(ir_graph *irg, int pos) { +size_t get_irg_caller_loop_depth(const ir_graph *irg, size_t pos) +{ ir_graph *caller = get_irg_caller(irg, pos); - int pos_callee = reverse_pos(irg, pos); + size_t pos_callee = reverse_pos(irg, pos); return get_irg_callee_loop_depth(caller, pos_callee); } - -/* Returns the number of procedures that are called by the given irg. */ -int get_irg_n_callees(ir_graph *irg) { - if (irg->callees) return ARR_LEN(irg->callees); - return -1; +size_t get_irg_n_callees(const ir_graph *irg) +{ + assert(irg->callees); + return irg->callees ? ARR_LEN(irg->callees) : 0; } -/* Returns the callee at position pos. */ -ir_graph *get_irg_callee(ir_graph *irg, int pos) { - assert(pos >= 0 && pos < get_irg_n_callees(irg)); - if (irg->callees) return irg->callees[pos]->irg; - return NULL; +ir_graph *get_irg_callee(const ir_graph *irg, size_t pos) +{ + assert(pos < get_irg_n_callees(irg)); + return irg->callees ? irg->callees[pos]->irg : NULL; } -/* Returns non-zero if the callee at position pos is "a backedge", i.e. a recursion. */ -int is_irg_callee_backedge(ir_graph *irg, int pos) { - assert(pos >= 0 && pos < get_irg_n_callees(irg)); +int is_irg_callee_backedge(const ir_graph *irg, size_t pos) +{ + assert(pos < get_irg_n_callees(irg)); return irg->callee_isbe != NULL ? rbitset_is_set(irg->callee_isbe, pos) : 0; } -/* Returns non-zero if the irg has a backedge callee. */ -int has_irg_callee_backedge(ir_graph *irg) { - int i, n_callees = get_irg_n_callees(irg); +int has_irg_callee_backedge(const ir_graph *irg) +{ + size_t i, n_callees = get_irg_n_callees(irg); if (irg->callee_isbe != NULL) { for (i = 0; i < n_callees; ++i) @@ -178,58 +166,30 @@ int has_irg_callee_backedge(ir_graph *irg) { /** * Mark the callee at position pos as a backedge. */ -static void set_irg_callee_backedge(ir_graph *irg, int pos) { - int n = get_irg_n_callees(irg); +static void set_irg_callee_backedge(ir_graph *irg, size_t pos) +{ + size_t n = get_irg_n_callees(irg); /* allocate a new array on demand */ if (irg->callee_isbe == NULL) irg->callee_isbe = rbitset_malloc(n); - assert(pos >= 0 && pos < n); + assert(pos < n); rbitset_set(irg->callee_isbe, pos); } -/* Returns the maximal loop depth of call nodes that call along this edge. */ -int get_irg_callee_loop_depth(ir_graph *irg, int pos) { - assert(pos >= 0 && pos < get_irg_n_callees(irg)); - if (irg->callees) return irg->callees[pos]->max_depth; - return -1; -} - - -double get_irg_callee_execution_frequency(ir_graph *irg, int pos) { - ir_node **arr = irg->callees[pos]->call_list; - int i, n_Calls = ARR_LEN(arr); - double freq = 0.0; - - for (i = 0; i < n_Calls; ++i) { - freq += get_irn_exec_freq(arr[i]); - } - return freq; -} - -double get_irg_callee_method_execution_frequency(ir_graph *irg, int pos) { - double call_freq = get_irg_callee_execution_frequency(irg, pos); - double meth_freq = get_irg_method_execution_frequency(irg); - return call_freq * meth_freq; -} - - -double get_irg_caller_method_execution_frequency(ir_graph *irg, int pos) { - ir_graph *caller = get_irg_caller(irg, pos); - int pos_callee = reverse_pos(irg, pos); - - return get_irg_callee_method_execution_frequency(caller, pos_callee); +size_t get_irg_callee_loop_depth(const ir_graph *irg, size_t pos) +{ + assert(pos < get_irg_n_callees(irg)); + return irg->callees ? irg->callees[pos]->max_depth : 0; } - -/* --------------------- Compute the callgraph ------------------------ */ - /** - * Walker called by compute_callgraph(), analyses all Call nodes. + * Pre-Walker called by compute_callgraph(), analyses all Call nodes. */ -static void ana_Call(ir_node *n, void *env) { - int i, n_callees; +static void ana_Call(ir_node *n, void *env) +{ + size_t i, n_callees; ir_graph *irg; (void) env; @@ -244,23 +204,23 @@ static void ana_Call(ir_node *n, void *env) { if (callee) { cg_callee_entry buf; cg_callee_entry *found; - int depth; + unsigned depth; buf.irg = callee; - pset_insert((pset *)callee->callers, irg, HASH_PTR(irg)); - found = pset_find((pset *)irg->callees, &buf, HASH_PTR(callee)); + pset_insert((pset *)callee->callers, irg, hash_ptr(irg)); + found = (cg_callee_entry*) pset_find((pset *)irg->callees, &buf, hash_ptr(callee)); if (found) { /* add Call node to list, compute new nesting. */ ir_node **arr = found->call_list; ARR_APP1(ir_node *, arr, n); found->call_list = arr; } else { /* New node, add Call node and init nesting. */ - found = (cg_callee_entry *)obstack_alloc(irg->obst, sizeof(*found)); + found = OALLOC(irg->obst, cg_callee_entry); found->irg = callee; found->call_list = NEW_ARR_F(ir_node *, 1); found->call_list[0] = n; found->max_depth = 0; - pset_insert((pset *)irg->callees, found, HASH_PTR(callee)); + pset_insert((pset *)irg->callees, found, hash_ptr(callee)); } depth = get_loop_depth(get_irn_loop(get_nodes_block(n))); found->max_depth = (depth > found->max_depth) ? depth : found->max_depth; @@ -269,27 +229,24 @@ static void ana_Call(ir_node *n, void *env) { } /** compare two ir graphs in a cg_callee_entry */ -static int cg_callee_entry_cmp(const void *elt, const void *key) { - const cg_callee_entry *e1 = elt; - const cg_callee_entry *e2 = key; +static int cg_callee_entry_cmp(const void *elt, const void *key) +{ + const cg_callee_entry *e1 = (const cg_callee_entry*) elt; + const cg_callee_entry *e2 = (const cg_callee_entry*) key; return e1->irg != e2->irg; } /** compare two ir graphs for pointer identity */ -static int graph_cmp(const void *elt, const void *key) { - const ir_graph *e1 = elt; - const ir_graph *e2 = key; +static int graph_cmp(const void *elt, const void *key) +{ + const ir_graph *e1 = (const ir_graph*) elt; + const ir_graph *e2 = (const ir_graph*) key; return e1 != e2; } - -/* Construct and destruct the callgraph. */ -void compute_callgraph(void) { - int i, n_irgs; - -#ifdef INTERPROCEDURAL_VIEW - assert(! get_interprocedural_view()); /* Else walking will not reach the Call nodes. */ -#endif +void compute_callgraph(void) +{ + size_t i, n_irgs; /* initialize */ free_callgraph(); @@ -312,7 +269,7 @@ void compute_callgraph(void) { /* Change the sets to arrays. */ for (i = 0; i < n_irgs; ++i) { - int j, count; + size_t j, count; cg_callee_entry *callee; ir_graph *c, *irg = get_irp_irg(i); pset *callee_set, *caller_set; @@ -321,10 +278,10 @@ void compute_callgraph(void) { count = pset_count(callee_set); irg->callees = NEW_ARR_F(cg_callee_entry *, count); irg->callee_isbe = NULL; - callee = pset_first(callee_set); + callee = (cg_callee_entry*) pset_first(callee_set); for (j = 0; j < count; ++j) { irg->callees[j] = callee; - callee = pset_next(callee_set); + callee = (cg_callee_entry*) pset_next(callee_set); } del_pset(callee_set); assert(callee == NULL); @@ -333,10 +290,10 @@ void compute_callgraph(void) { count = pset_count(caller_set); irg->callers = NEW_ARR_F(ir_graph *, count); irg->caller_isbe = NULL; - c = pset_first(caller_set); + c = (ir_graph*) pset_first(caller_set); for (j = 0; j < count; ++j) { irg->callers[j] = c; - c = pset_next(caller_set); + c = (ir_graph*) pset_next(caller_set); } del_pset(caller_set); assert(c == NULL); @@ -344,9 +301,9 @@ void compute_callgraph(void) { set_irp_callgraph_state(irp_callgraph_consistent); } -/* Destruct the callgraph. */ -void free_callgraph(void) { - int i, n_irgs = get_irp_n_irgs(); +void free_callgraph(void) +{ + size_t i, n_irgs = get_irp_n_irgs(); for (i = 0; i < n_irgs; ++i) { ir_graph *irg = get_irp_irg(i); if (irg->callees) DEL_ARR_F(irg->callees); @@ -361,13 +318,10 @@ void free_callgraph(void) { set_irp_callgraph_state(irp_callgraph_none); } -/* ----------------------------------------------------------------------------------- */ -/* A walker for the callgraph */ -/* ----------------------------------------------------------------------------------- */ - -static void do_walk(ir_graph *irg, callgraph_walk_func *pre, callgraph_walk_func *post, void *env) { - int i, n_callees; +static void do_walk(ir_graph *irg, callgraph_walk_func *pre, callgraph_walk_func *post, void *env) +{ + size_t i, n_callees; if (cg_irg_visited(irg)) return; @@ -386,146 +340,140 @@ static void do_walk(ir_graph *irg, callgraph_walk_func *pre, callgraph_walk_func post(irg, env); } -void callgraph_walk(callgraph_walk_func *pre, callgraph_walk_func *post, void *env) { - int i, n_irgs = get_irp_n_irgs(); +void callgraph_walk(callgraph_walk_func *pre, callgraph_walk_func *post, void *env) +{ + size_t i, n_irgs = get_irp_n_irgs(); ++master_cg_visited; - do_walk(get_irp_main_irg(), pre, post, env); - for (i = 0; i < n_irgs; i++) { + /* roots are methods which have no callers in the current program */ + for (i = 0; i < n_irgs; ++i) { ir_graph *irg = get_irp_irg(i); - if (!cg_irg_visited(irg) && get_irg_n_callers(irg) == 0) + + if (get_irg_n_callers(irg) == 0) do_walk(irg, pre, post, env); } + + /* in case of unreachable call loops we haven't visited some irgs yet */ for (i = 0; i < n_irgs; i++) { ir_graph *irg = get_irp_irg(i); - if (!cg_irg_visited(irg)) - do_walk(irg, pre, post, env); + do_walk(irg, pre, post, env); } } -/* ----------------------------------------------------------------------------------- */ -/* loop construction algorithm */ -/* ----------------------------------------------------------------------------------- */ - static ir_graph *outermost_ir_graph; /**< The outermost graph the scc is computed for */ static ir_loop *current_loop; /**< Current cfloop construction is working on. */ -static int loop_node_cnt = 0; /**< Counts the number of allocated cfloop nodes. +static size_t loop_node_cnt = 0; /**< Counts the number of allocated cfloop nodes. Each cfloop node gets a unique number. What for? ev. remove. @@@ */ -static int current_dfn = 1; /**< Counter to generate depth first numbering +static size_t current_dfn = 1; /**< Counter to generate depth first numbering of visited nodes. */ -/*-----------------*/ -/* Node attributes */ -/*-----------------*/ - typedef struct scc_info { + size_t dfn; /**< Depth first search number. */ + size_t uplink; /**< dfn number of ancestor. */ + ir_visited_t visited; /**< visited counter */ int in_stack; /**< Marks whether node is on the stack. */ - int dfn; /**< Depth first search number. */ - int uplink; /**< dfn number of ancestor. */ - int visited; } scc_info; /** * allocates a new scc_info on the obstack */ -static INLINE scc_info *new_scc_info(struct obstack *obst) { - scc_info *info = obstack_alloc(obst, sizeof(*info)); - memset(info, 0, sizeof(*info)); - return info; +static inline scc_info *new_scc_info(struct obstack *obst) +{ + return OALLOCZ(obst, scc_info); } /** * Returns non-zero if a graph was already visited. */ -static INLINE int cg_irg_visited(ir_graph *irg) { - scc_info *info = get_irg_link(irg); - assert(info && "missing call to init_scc()"); - return info->visited >= master_cg_visited; +static inline int cg_irg_visited(ir_graph *irg) +{ + return irg->self_visited >= master_cg_visited; } /** * Marks a graph as visited. */ -static INLINE void mark_cg_irg_visited(ir_graph *irg) { - scc_info *info = get_irg_link(irg); - assert(info && "missing call to init_scc()"); - info->visited = master_cg_visited; +static inline void mark_cg_irg_visited(ir_graph *irg) +{ + irg->self_visited = master_cg_visited; } /** * Set a graphs visited flag to i. */ -static INLINE void set_cg_irg_visited(ir_graph *irg, int i) { - scc_info *info = get_irg_link(irg); - assert(info && "missing call to init_scc()"); - info->visited = i; +static inline void set_cg_irg_visited(ir_graph *irg, ir_visited_t i) +{ + irg->self_visited = i; } /** * Returns the visited flag of a graph. */ -static INLINE int get_cg_irg_visited(ir_graph *irg) { - scc_info *info = get_irg_link(irg); - assert(info && "missing call to init_scc()"); - return info->visited; +static inline ir_visited_t get_cg_irg_visited(const ir_graph *irg) +{ + return irg->self_visited; } -static INLINE void mark_irg_in_stack(ir_graph *irg) { - scc_info *info = get_irg_link(irg); +static inline void mark_irg_in_stack(ir_graph *irg) +{ + scc_info *info = (scc_info*) get_irg_link(irg); assert(info && "missing call to init_scc()"); info->in_stack = 1; } -static INLINE void mark_irg_not_in_stack(ir_graph *irg) { - scc_info *info = get_irg_link(irg); +static inline void mark_irg_not_in_stack(ir_graph *irg) +{ + scc_info *info = (scc_info*) get_irg_link(irg); assert(info && "missing call to init_scc()"); info->in_stack = 0; } -static INLINE int irg_is_in_stack(ir_graph *irg) { - scc_info *info = get_irg_link(irg); +static inline int irg_is_in_stack(const ir_graph *irg) +{ + scc_info *info = (scc_info*) get_irg_link(irg); assert(info && "missing call to init_scc()"); return info->in_stack; } -static INLINE void set_irg_uplink(ir_graph *irg, int uplink) { - scc_info *info = get_irg_link(irg); +static inline void set_irg_uplink(ir_graph *irg, size_t uplink) +{ + scc_info *info = (scc_info*) get_irg_link(irg); assert(info && "missing call to init_scc()"); info->uplink = uplink; } -static INLINE int get_irg_uplink(ir_graph *irg) { - scc_info *info = get_irg_link(irg); +static inline size_t get_irg_uplink(const ir_graph *irg) +{ + const scc_info *info = (scc_info*) get_irg_link(irg); assert(info && "missing call to init_scc()"); return info->uplink; } -static INLINE void set_irg_dfn(ir_graph *irg, int dfn) { - scc_info *info = get_irg_link(irg); +static inline void set_irg_dfn(ir_graph *irg, size_t dfn) +{ + scc_info *info = (scc_info*) get_irg_link(irg); assert(info && "missing call to init_scc()"); info->dfn = dfn; } -static INLINE int get_irg_dfn(ir_graph *irg) { - scc_info *info = get_irg_link(irg); +static inline size_t get_irg_dfn(const ir_graph *irg) +{ + const scc_info *info = (scc_info*) get_irg_link(irg); assert(info && "missing call to init_scc()"); return info->dfn; } -/**********************************************************************/ -/* A stack. **/ -/**********************************************************************/ - static ir_graph **stack = NULL; -static int tos = 0; /**< top of stack */ +static size_t tos = 0; /**< top of stack */ /** * Initialize the irg stack. */ -static INLINE void init_stack(void) { +static inline void init_stack(void) +{ if (stack) { ARR_RESIZE(ir_graph *, stack, 1000); } else { @@ -538,10 +486,11 @@ static INLINE void init_stack(void) { * push a graph on the irg stack * @param n the graph to be pushed */ -static INLINE void push(ir_graph *irg) { +static inline void push(ir_graph *irg) +{ if (tos == ARR_LEN(stack)) { - int nlen = ARR_LEN(stack) * 2; - ARR_RESIZE(ir_node *, stack, nlen); + size_t nlen = ARR_LEN(stack) * 2; + ARR_RESIZE(ir_graph*, stack, nlen); } stack [tos++] = irg; mark_irg_in_stack(irg); @@ -550,8 +499,12 @@ static INLINE void push(ir_graph *irg) { /** * return the topmost graph on the stack and pop it */ -static INLINE ir_graph *pop(void) { - ir_graph *irg = stack[--tos]; +static inline ir_graph *pop(void) +{ + ir_graph *irg; + + assert(tos > 0); + irg = stack[--tos]; mark_irg_not_in_stack(irg); return irg; } @@ -560,24 +513,26 @@ static INLINE ir_graph *pop(void) { * The nodes up to irg belong to the current loop. * Removes them from the stack and adds them to the current loop. */ -static INLINE void pop_scc_to_loop(ir_graph *irg) { +static inline void pop_scc_to_loop(ir_graph *irg) +{ ir_graph *m; do { m = pop(); - loop_node_cnt++; + ++loop_node_cnt; set_irg_dfn(m, loop_node_cnt); - add_loop_node(current_loop, (ir_node *)m); + add_loop_irg(current_loop, m); m->l = current_loop; //m->callgraph_loop_depth = current_loop->depth; - } while(m != irg); + } while (m != irg); } /* GL ??? my last son is my grandson??? Removes cfloops with no ir_nodes in them. Such loops have only another loop as son. (Why can't they have two loops as sons? Does it never get that far? ) */ -static void close_loop(ir_loop *l) { - int last = get_loop_n_elements(l) - 1; +static void close_loop(ir_loop *l) +{ + size_t last = get_loop_n_elements(l) - 1; loop_element lelement = get_loop_element(l, last); ir_loop *last_son = lelement.son; @@ -602,7 +557,8 @@ static void close_loop(ir_loop *l) { * Removes and unmarks all nodes up to n from the stack. * The nodes must be visited once more to assign them to a scc. */ -static INLINE void pop_scc_unmark_visit(ir_graph *n) { +static inline void pop_scc_unmark_visit(ir_graph *n) +{ ir_graph *m = NULL; while (m != n) { @@ -611,15 +567,12 @@ static INLINE void pop_scc_unmark_visit(ir_graph *n) { } } -/**********************************************************************/ -/* The loop data structure. **/ -/**********************************************************************/ - /** * Allocates a new loop as son of current_loop. Sets current_loop * to the new loop and returns the father. */ -static ir_loop *new_loop(void) { +static ir_loop *new_loop(void) +{ ir_loop *father = current_loop; ir_loop *son = alloc_loop(father, outermost_ir_graph->obst); @@ -628,15 +581,9 @@ static ir_loop *new_loop(void) { } -/**********************************************************************/ -/* Constructing and destructing the loop/backedge information. **/ -/**********************************************************************/ - -/* Initialization steps. **********************************************/ - -static void init_scc(struct obstack *obst) { - int i; - int n_irgs; +static void init_scc(struct obstack *obst) +{ + size_t i, n_irgs; current_dfn = 1; loop_node_cnt = 0; @@ -656,13 +603,14 @@ static void init_scc(struct obstack *obst) { * * @param root: only needed for assertion. */ -static int is_head(ir_graph *n, ir_graph *root) { - int i, arity; +static int is_head(const ir_graph *n, const ir_graph *root) +{ + size_t i, n_callees; int some_outof_loop = 0, some_in_loop = 0; - arity = get_irg_n_callees(n); - for (i = 0; i < arity; i++) { - ir_graph *pred = get_irg_callee(n, i); + n_callees = get_irg_n_callees(n); + for (i = 0; i < n_callees; ++i) { + const ir_graph *pred = get_irg_callee(n, i); if (is_irg_callee_backedge(n, i)) continue; if (!irg_is_in_stack(pred)) { some_outof_loop = 1; @@ -674,23 +622,23 @@ static int is_head(ir_graph *n, ir_graph *root) { } } - return some_outof_loop & some_in_loop; + return some_outof_loop && some_in_loop; } /** * Returns non-zero if n is possible loop head of an endless loop. - * I.e., it is a Block, Phi or Filter node and has only predecessors + * I.e., it is a Block or Phi node and has only predecessors * within the loop. * @arg root: only needed for assertion. */ -static int is_endless_head(ir_graph *n, ir_graph *root) +static int is_endless_head(const ir_graph *n, const ir_graph *root) { - int i, arity; + size_t i, n_calless; int some_outof_loop = 0, some_in_loop = 0; - arity = get_irg_n_callees(n); - for (i = 0; i < arity; i++) { - ir_graph *pred = get_irg_callee(n, i); + n_calless = get_irg_n_callees(n); + for (i = 0; i < n_calless; ++i) { + const ir_graph *pred = get_irg_callee(n, i); assert(pred); if (is_irg_callee_backedge(n, i)) continue; @@ -703,221 +651,121 @@ static int is_endless_head(ir_graph *n, ir_graph *root) some_in_loop = 1; } } - return !some_outof_loop & some_in_loop; -} - -#ifdef INTERPROCEDURAL_VIEW -/** - * Check whether there is a parallel edge in the ip control flow. - * Only - */ -static int is_ip_head(ir_graph *n, ir_graph *pred) -{ - int is_be = 0; - - int iv_rem = get_interprocedural_view(); - set_interprocedural_view(1); - { - ir_node *sblock = get_irg_start_block(n); - int i, arity = get_Block_n_cfgpreds(sblock); - - //printf(" edge from "); DDMG(n); - //printf(" to pred "); DDMG(pred); - //printf(" sblock "); DDMN(sblock); - - for (i = 0; i < arity; i++) { - ir_node *pred_cfop = skip_Proj(get_Block_cfgpred(sblock, i)); - //printf(" "); DDMN(pred_cfop); - if (get_irn_op(pred_cfop) == op_CallBegin) { /* could be Unknown */ - ir_graph *ip_pred = get_irn_irg(pred_cfop); - //printf(" "); DDMG(ip_pred); - if ((ip_pred == pred) && is_backedge(sblock, i)) { - //printf(" found\n"); - is_be = 1; - } - } - } - } - set_interprocedural_view(iv_rem); - return is_be; + return !some_outof_loop && some_in_loop; } -#endif /* INTERPROCEDURAL_VIEW */ /** - * Returns index of the predecessor with the smallest dfn number + * Finds index of the predecessor with the smallest dfn number * greater-equal than limit. */ -static int smallest_dfn_pred(ir_graph *n, int limit) +static bool smallest_dfn_pred(const ir_graph *n, size_t limit, size_t *result) { - int i, index = -2, min = -1; + size_t index = 0, min = 0; + bool found = false; - int arity = get_irg_n_callees(n); - for (i = 0; i < arity; i++) { - ir_graph *pred = get_irg_callee(n, i); + size_t i, n_callees = get_irg_n_callees(n); + for (i = 0; i < n_callees; ++i) { + const ir_graph *pred = get_irg_callee(n, i); if (is_irg_callee_backedge(n, i) || !irg_is_in_stack(pred)) continue; - if (get_irg_dfn(pred) >= limit && (min == -1 || get_irg_dfn(pred) < min)) { + if (get_irg_dfn(pred) >= limit && (!found || get_irg_dfn(pred) < min)) { index = i; min = get_irg_dfn(pred); + found = true; } } - return index; + *result = index; + return found; } -/** Returns index of the predecessor with the largest dfn number. */ -static int largest_dfn_pred(ir_graph *n) { - int i, index = -2, max = -1; +/** Finds index of the predecessor with the largest dfn number. */ +static bool largest_dfn_pred(const ir_graph *n, size_t *result) +{ + size_t index = 0, max = 0; + bool found = false; - int arity = get_irg_n_callees(n); - for (i = 0; i < arity; ++i) { - ir_graph *pred = get_irg_callee(n, i); - if (is_irg_callee_backedge (n, i) || !irg_is_in_stack(pred)) continue; + size_t i, n_callees = get_irg_n_callees(n); + for (i = 0; i < n_callees; ++i) { + const ir_graph *pred = get_irg_callee(n, i); + if (is_irg_callee_backedge (n, i) || !irg_is_in_stack(pred)) + continue; + /* Note: dfn is always > 0 */ if (get_irg_dfn(pred) > max) { index = i; max = get_irg_dfn(pred); + found = true; } } - return index; + *result = index; + return found; } -#ifndef INTERPROCEDURAL_VIEW -static ir_graph *find_tail(ir_graph *n) { +static ir_graph *find_tail(const ir_graph *n) +{ + bool found = false; ir_graph *m; - int i, res_index = -2; + size_t i, res_index; /* if (!icfg && rm_cyclic_phis && remove_cyclic_phis (n)) return NULL; */ - m = stack[tos-1]; /* tos = top of stack */ - if (is_head (m, n)) { - res_index = smallest_dfn_pred(m, 0); - if ((res_index == -2) && /* no smallest dfn pred found. */ - (n == m)) + m = stack[tos - 1]; /* tos = top of stack */ + if (is_head(m, n)) { + found = smallest_dfn_pred(m, 0, &res_index); + if (!found && /* no smallest dfn pred found. */ + n == m) return NULL; } else { if (m == n) return NULL; // Is this to catch Phi - self loops? - for (i = tos-2; i >= 0; --i) { - m = stack[i]; + for (i = tos - 1; i > 0;) { + m = stack[--i]; if (is_head(m, n)) { - res_index = smallest_dfn_pred(m, get_irg_dfn(m) + 1); - if (res_index == -2) /* no smallest dfn pred found. */ - res_index = largest_dfn_pred(m); + found = smallest_dfn_pred(m, get_irg_dfn(m) + 1, &res_index); + if (! found) /* no smallest dfn pred found. */ + found = largest_dfn_pred(m, &res_index); - if ((m == n) && (res_index == -2)) { - i = -1; - } break; } /* We should not walk past our selves on the stack: The upcoming nodes are not in this loop. We assume a loop not reachable from Start. */ if (m == n) { - i = -1; + found = false; break; } } - if (i < 0) { + if (! found) { /* A dead loop not reachable from Start. */ - for (i = tos-2; i >= 0; --i) { - m = stack[i]; + for (i = tos-1; i > 0;) { + m = stack[--i]; if (is_endless_head(m, n)) { - res_index = smallest_dfn_pred(m, get_irg_dfn(m) + 1); - if (res_index == -2) /* no smallest dfn pred found. */ - res_index = largest_dfn_pred(m); + found = smallest_dfn_pred(m, get_irg_dfn(m) + 1, &res_index); + if (!found) /* no smallest dfn pred found. */ + found = largest_dfn_pred(m, &res_index); break; } - if (m == n) { break; } /* It's not an unreachable loop, either. */ + /* It's not an unreachable loop, either. */ + if (m == n) + break; } //assert(0 && "no head found on stack"); } } - assert (res_index > -2); + assert(found); set_irg_callee_backedge(m, res_index); return get_irg_callee(m, res_index); } -#else -static ir_graph *find_tail(ir_graph *n) { - ir_graph *m; - int i, res_index = -2; - - ir_graph *res; - ir_graph *in_and_out = NULL; - ir_graph *only_in = NULL; - ir_graph *ip_in_and_out = NULL; - ir_graph *ip_only_in = NULL; - - //printf("find tail for "); DDMG(n); - - for (i = tos-1; i >= 0; --i) { - ir_graph *pred = (i < tos -1) ? stack[i+1] : n; - m = stack[i]; - - if (is_head(m, n)) { - //printf(" found 1a! "); DDM; - in_and_out = m; - if (is_ip_head(pred, m)) { - //printf(" found 1b! "); DDM; - ip_in_and_out = m; - } - } else if (!ip_only_in && is_endless_head(m, n)) { - only_in = m; - //printf(" found 2a! "); DDM; - if (is_ip_head(pred, m)) { - //printf(" found 2b! "); DDM; - ip_only_in = m; - } - } else if (is_ip_head(pred, m)) { - //printf(" found 3! "); DDM; This happens for self recursions in the second - //assert(0); scc iteration (the one to flip the loop.) - } - - if (ip_in_and_out) break; /* That's what we really want. */ - - if (m == n) break; /* Don't walk past n on the stack! */ - } - - - if (!in_and_out && !only_in) - /* There is no loop */ - return NULL; - - /* Is there a head in the callgraph without a head in the - ip cf graph? */ - assert(in_and_out || only_in); - - m = (ip_in_and_out) ? ip_in_and_out : ip_only_in; - - if (!m) - m = (in_and_out) ? in_and_out : only_in; - - //printf("*** head is "); DDMG(m); - - res_index = smallest_dfn_pred(m, get_irg_dfn(m) + 1); - if (res_index == -2) /* no smallest dfn pred found. */ - res_index = largest_dfn_pred(m); - - set_irg_callee_backedge(m, res_index); - res = get_irg_callee(m, res_index); - //printf("*** tail is "); DDMG(res); - return res; -} -#endif /* INTERPROCEDURAL_VIEW */ - -/*-----------------------------------------------------------* - * The core algorithm. * - *-----------------------------------------------------------*/ - - -static void cgscc(ir_graph *n) { - int i, arity; +static void cgscc(ir_graph *n) +{ + size_t i, n_callees; if (cg_irg_visited(n)) return; mark_cg_irg_visited(n); @@ -925,11 +773,11 @@ static void cgscc(ir_graph *n) { /* Initialize the node */ set_irg_dfn(n, current_dfn); /* Depth first number for this node */ set_irg_uplink(n, current_dfn); /* ... is default uplink. */ - current_dfn ++; + ++current_dfn; push(n); - arity = get_irg_n_callees(n); - for (i = 0; i < arity; i++) { + n_callees = get_irg_n_callees(n); + for (i = 0; i < n_callees; ++i) { ir_graph *m; if (is_irg_callee_backedge(n, i)) continue; m = get_irg_callee(n, i); @@ -937,7 +785,7 @@ static void cgscc(ir_graph *n) { /** This marks the backedge, but does it guarantee a correct loop tree? */ //if (m == n) { set_irg_callee_backedge(n, i); continue; } - cgscc (m); + cgscc(m); if (irg_is_in_stack(m)) { /* Uplink of m is smaller if n->m is a backedge. Propagate the uplink to mark the cfloop. */ @@ -990,8 +838,9 @@ static void cgscc(ir_graph *n) { /** * reset the backedge information for all callers in all irgs */ -static void reset_isbe(void) { - int i, n_irgs = get_irp_n_irgs(); +static void reset_isbe(void) +{ + size_t i, n_irgs = get_irp_n_irgs(); for (i = 0; i < n_irgs; ++i) { ir_graph *irg = get_irp_irg(i); @@ -1006,219 +855,9 @@ static void reset_isbe(void) { } } -/* ----------------------------------------------------------------------------------- */ -/* Another algorithm to compute recursion nesting depth */ -/* Walk the callgraph. For each crossed edge increase the loop depth by the edge */ -/* weight. Assign graphs the maximal depth. */ -/* ----------------------------------------------------------------------------------- */ - -static void compute_loop_depth(ir_graph *irg, void *env) { - int current_nesting = *(int *) env; - int old_nesting = irg->callgraph_loop_depth; - int old_visited = get_cg_irg_visited(irg); - int i, n_callees; - - //return ; - - if (cg_irg_visited(irg)) return; - - mark_cg_irg_visited(irg); - - //printf(" old: %d new %d master %d", old_visited, get_cg_irg_visited(irg), master_cg_visited); DDMG(irg); - - - if (old_nesting < current_nesting) - irg->callgraph_loop_depth = current_nesting; - - if (current_nesting > irp->max_callgraph_loop_depth) - irp->max_callgraph_loop_depth = current_nesting; - - if ((old_visited +1 < get_cg_irg_visited(irg)) || /* not yet visited */ - (old_nesting < current_nesting)) { /* propagate larger nesting */ - /* Don't walk the graph, but a tree that is an unfolded graph. */ - n_callees = get_irg_n_callees(irg); - for (i = 0; i < n_callees; i++) { - ir_graph *m = get_irg_callee(irg, i); - *(int *)env += get_irg_callee_loop_depth(irg, i); - compute_loop_depth(m, env); - *(int *)env -= get_irg_callee_loop_depth(irg, i); - } - } - - set_cg_irg_visited(irg, master_cg_visited-1); -} - -/* ------------------------------------------------------------------------------------ */ -/* Another algorithm to compute recursion nesting depth */ -/* Walk the callgraph. For each crossed loop increase the nesting depth by one. */ -/* Assign graphs the maximal nesting depth. Don't increase if passing loops more than */ -/* once. */ -/* ------------------------------------------------------------------------------------ */ - - -/* For callees, we want to remember the Call nodes, too. */ -typedef struct ana_entry2 { - ir_loop **loop_stack; /**< a stack of ir_loop entries */ - int tos; /**< the top of stack entry */ - int recursion_nesting; -} ana_entry2; - -/** - * push a loop entry on the stack - */ -static void push2(ana_entry2 *e, ir_loop *g) { - if (ARR_LEN(e->loop_stack) == e->tos) { - ARR_APP1(ir_loop *, e->loop_stack, g); - } else { - e->loop_stack[e->tos] = g; - } - ++e->tos; -} - -/** - * returns the top of stack and pop it - */ -static ir_loop *pop2(ana_entry2 *e) { - return e->loop_stack[--e->tos]; -} - -/** - * check if a loop g in on the stack. Did not check the TOS. - */ -static int in_stack(ana_entry2 *e, ir_loop *g) { - int i; - for (i = e->tos-1; i >= 0; --i) { - if (e->loop_stack[i] == g) return 1; - } - return 0; -} - -static void compute_rec_depth(ir_graph *irg, void *env) { - ana_entry2 *e = (ana_entry2 *)env; - ir_loop *l = irg->l; - int depth, old_depth = irg->callgraph_recursion_depth; - int i, n_callees; - int pushed = 0; - - if (cg_irg_visited(irg)) - return; - mark_cg_irg_visited(irg); - - /* -- compute and set the new nesting value -- */ - if ((l != irp->outermost_cg_loop) && !in_stack(e, l)) { - push2(e, l); - e->recursion_nesting++; - pushed = 1; - } - depth = e->recursion_nesting; - - if (old_depth < depth) - irg->callgraph_recursion_depth = depth; - - if (depth > irp->max_callgraph_recursion_depth) - irp->max_callgraph_recursion_depth = depth; - - /* -- spread the nesting value -- */ - if (depth == 0 || old_depth < depth) { - /* Don't walk the graph, but a tree that is an unfolded graph. - Therefore we unset the visited flag at the end. */ - n_callees = get_irg_n_callees(irg); - for (i = 0; i < n_callees; ++i) { - ir_graph *m = get_irg_callee(irg, i); - compute_rec_depth(m, env); - } - } - - /* -- clean up -- */ - if (pushed) { - pop2(e); - e->recursion_nesting--; - } - set_cg_irg_visited(irg, master_cg_visited-1); -} - - -/* ----------------------------------------------------------------------------------- */ -/* Another algorithm to compute the execution frequency of methods ignoring recursions. */ -/* Walk the callgraph. Ignore backedges. Use sum of execution frequencies of Call */ -/* nodes to evaluate a callgraph edge. */ -/* ----------------------------------------------------------------------------------- */ - -/* Returns the method execution frequency of a graph. */ -double get_irg_method_execution_frequency(ir_graph *irg) { - return irg->method_execution_frequency; -} - -/** - * Increase the method execution frequency to freq if its current value is - * smaller then this. - */ -static void set_irg_method_execution_frequency(ir_graph *irg, double freq) { - irg->method_execution_frequency = freq; - - if (irp->max_method_execution_frequency < freq) - irp->max_method_execution_frequency = freq; -} - -static void compute_method_execution_frequency(ir_graph *irg, void *env) { - int i, n_callers; - double freq; - int found_edge; - int n_callees; - (void) env; - - if (cg_irg_visited(irg)) - return; - - /* We need the values of all predecessors (except backedges). - So they must be marked. Else we will reach the node through - one of the unmarked ones. */ - n_callers = get_irg_n_callers(irg); - for (i = 0; i < n_callers; ++i) { - ir_graph *m = get_irg_caller(irg, i); - if (is_irg_caller_backedge(irg, i)) - continue; - if (!cg_irg_visited(m)) { - return; - } - } - mark_cg_irg_visited(irg); - - /* Compute the new frequency. */ - freq = 0; - found_edge = 0; - for (i = 0; i < n_callers; i++) { - if (! is_irg_caller_backedge(irg, i)) { - double edge_freq = get_irg_caller_method_execution_frequency(irg, i); - assert(edge_freq >= 0); - freq += edge_freq; - found_edge = 1; - } - } - - if (!found_edge) { - /* A starting point: method only called from outside, - or only backedges as predecessors. */ - freq = 1; - } - - set_irg_method_execution_frequency(irg, freq); - - /* recur */ - n_callees = get_irg_n_callees(irg); - for (i = 0; i < n_callees; ++i) { - compute_method_execution_frequency(get_irg_callee(irg, i), NULL); - } -} - - -/* ----------------------------------------------------------------------------------- */ -/* The recursion stuff driver. */ -/* ----------------------------------------------------------------------------------- */ - -/* Compute the backedges that represent recursions. */ -void find_callgraph_recursions(void) { - int i, n_irgs = get_irp_n_irgs(); +void find_callgraph_recursions(void) +{ + size_t i, n_irgs; struct obstack temp; reset_isbe(); @@ -1239,6 +878,7 @@ void find_callgraph_recursions(void) { ++master_cg_visited; cgscc(outermost_ir_graph); + n_irgs = get_irp_n_irgs(); for (i = 0; i < n_irgs; ++i) { ir_graph *irg = get_irp_irg(i); if (!cg_irg_visited(irg) && get_irg_n_callers(irg) == 0) @@ -1257,7 +897,7 @@ void find_callgraph_recursions(void) { /* -- Reverse the backedge information. -- */ for (i = 0; i < n_irgs; ++i) { ir_graph *irg = get_irp_irg(i); - int j, n_callees = get_irg_n_callees(irg); + size_t j, n_callees = get_irg_n_callees(irg); for (j = 0; j < n_callees; ++j) { if (is_irg_callee_backedge(irg, j)) set_irg_caller_backedge(get_irg_callee(irg, j), irg); @@ -1267,108 +907,27 @@ void find_callgraph_recursions(void) { irp->callgraph_state = irp_callgraph_and_calltree_consistent; } -/* Compute interprocedural performance estimates. */ -void compute_performance_estimates(void) { - int i, n_irgs = get_irp_n_irgs(); - int current_nesting; - ana_entry2 e; - - assert(get_irp_exec_freq_state() != exec_freq_none && "execution frequency not calculated"); - - /* -- compute the loop depth -- */ - current_nesting = 0; - irp->max_callgraph_loop_depth = 0; - master_cg_visited += 2; - //printf(" ** starting at "); DDMG(get_irp_main_irg()); - compute_loop_depth(get_irp_main_irg(), ¤t_nesting); - for (i = 0; i < n_irgs; i++) { - ir_graph *irg = get_irp_irg(i); - if ((get_cg_irg_visited(irg) < master_cg_visited-1) && - get_irg_n_callers(irg) == 0) { - compute_loop_depth(irg, ¤t_nesting); - //printf(" ** starting at "); DDMG(irg); - } - } - for (i = 0; i < n_irgs; i++) { - ir_graph *irg = get_irp_irg(i); - if (get_cg_irg_visited(irg) < master_cg_visited-1) { - compute_loop_depth(irg, ¤t_nesting); - //printf(" ** starting at "); DDMG(irg); - } - } - - - /* -- compute the recursion depth -- */ - e.loop_stack = NEW_ARR_F(ir_loop *, 0); - e.tos = 0; - e.recursion_nesting = 0; - - irp->max_callgraph_recursion_depth = 0; - - master_cg_visited += 2; - compute_rec_depth(get_irp_main_irg(), &e); - //printf(" ++ starting at "); DDMG(get_irp_main_irg()); - for (i = 0; i < n_irgs; i++) { - ir_graph *irg = get_irp_irg(i); - if ((get_cg_irg_visited(irg) < master_cg_visited-1) && - get_irg_n_callers(irg) == 0) { - compute_rec_depth(irg, &e); - //printf(" ++ starting at "); DDMG(irg); - } - } - for (i = 0; i < n_irgs; i++) { - ir_graph *irg = get_irp_irg(i); - if (get_cg_irg_visited(irg) < master_cg_visited-1) { - compute_rec_depth(irg, &e); - //printf(" ++ starting at "); DDMG(irg); - } - } - - DEL_ARR_F(e.loop_stack); - - /* -- compute the execution frequency -- */ - irp->max_method_execution_frequency = 0; - master_cg_visited += 2; - assert(get_irg_n_callers(get_irp_main_irg()) == 0); - compute_method_execution_frequency(get_irp_main_irg(), NULL); - for (i = 0; i < n_irgs; i++) { - ir_graph *irg = get_irp_irg(i); - if ((get_cg_irg_visited(irg) < master_cg_visited-1) && - get_irg_n_callers(irg) == 0) { - compute_method_execution_frequency(irg, NULL); - } - } - for (i = 0; i < n_irgs; i++) { - ir_graph *irg = get_irp_irg(i); - if (get_cg_irg_visited(irg) < master_cg_visited-1) { - compute_method_execution_frequency(irg, NULL); - } - } -} - -/* Returns the maximal loop depth of all paths from an external visible method to - this irg. */ -int get_irg_loop_depth(ir_graph *irg) { +size_t get_irg_loop_depth(const ir_graph *irg) +{ assert(irp->callgraph_state == irp_callgraph_consistent || irp->callgraph_state == irp_callgraph_and_calltree_consistent); - return irg->callgraph_loop_depth; + return irg->callgraph_loop_depth; } -/* Returns the maximal recursion depth of all paths from an external visible method to - this irg. */ -int get_irg_recursion_depth(ir_graph *irg) { +size_t get_irg_recursion_depth(const ir_graph *irg) +{ assert(irp->callgraph_state == irp_callgraph_and_calltree_consistent); return irg->callgraph_recursion_depth; } -/* Computes the interprocedural loop nesting information. */ -void analyse_loop_nesting_depth(void) { - ir_entity **free_methods = NULL; - int arr_len; - +void analyse_loop_nesting_depth(void) +{ /* establish preconditions. */ if (get_irp_callee_info_state() != irg_callee_info_consistent) { - cgana(&arr_len, &free_methods); + ir_entity **free_methods = NULL; + + cgana(&free_methods); + xfree(free_methods); } if (irp_callgraph_consistent != get_irp_callgraph_state()) { @@ -1377,18 +936,19 @@ void analyse_loop_nesting_depth(void) { find_callgraph_recursions(); - compute_performance_estimates(); - set_irp_loop_nesting_depth_state(loop_nesting_depth_consistent); } -loop_nesting_depth_state get_irp_loop_nesting_depth_state(void) { +loop_nesting_depth_state get_irp_loop_nesting_depth_state(void) +{ return irp->lnd_state; } -void set_irp_loop_nesting_depth_state(loop_nesting_depth_state s) { +void set_irp_loop_nesting_depth_state(loop_nesting_depth_state s) +{ irp->lnd_state = s; } -void set_irp_loop_nesting_depth_state_inconsistent(void) { +void set_irp_loop_nesting_depth_state_inconsistent(void) +{ if (irp->lnd_state == loop_nesting_depth_consistent) irp->lnd_state = loop_nesting_depth_inconsistent; }