+
+
+
+/* ----------------------------------------------------------------------------------- */
+/* 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. */
+/* ----------------------------------------------------------------------------------- */
+
+double get_irg_method_execution_frequency (ir_graph *irg) {
+ return irg->method_execution_frequency;
+}
+
+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;
+
+ 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. */
+/* ----------------------------------------------------------------------------------- */
+