+/**
+ * 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. */
+/* ----------------------------------------------------------------------------------- */
+