[deliverable/binutils-gdb.git] / gprof / cg_dfn.c

/*
 * Copyright (c) 1983 Regents of the University of California.
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms are permitted
 * provided that: (1) source distributions retain this entire copyright
 * notice and comment, and (2) distributions including binaries display
 * the following acknowledgement:  ``This product includes software
 * developed by the University of California, Berkeley and its contributors''
 * in the documentation or other materials provided with the distribution
 * and in all advertising materials mentioning features or use of this
 * software. Neither the name of the University nor the names of its
 * contributors may be used to endorse or promote products derived
 * from this software without specific prior written permission.
 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
 */
#include <stdio.h>
#include "gprof.h"
#include "cg_arcs.h"
#include "cg_dfn.h"
#include "symtab.h"
#include "utils.h"

#define	DFN_DEPTH	100

typedef struct {
    Sym *sym;
    int cycle_top;
} DFN_Stack;

DFN_Stack dfn_stack[DFN_DEPTH];
int	dfn_depth = 0;
int	dfn_counter = DFN_NAN;


/*
 * Is CHILD already numbered?
 */
static bool
DEFUN(is_numbered, (child), Sym *child)
{
    return child->cg.top_order != DFN_NAN && child->cg.top_order != DFN_BUSY;
} /* is_numbered */


/*
 * Is CHILD already busy?
 */
static bool
DEFUN(is_busy, (child), Sym *child)
{
    if (child->cg.top_order == DFN_NAN) {
	return FALSE;
    } /* if */
    return TRUE;
} /* is_busy */


/*
 * CHILD is part of a cycle.  Find the top caller into this cycle
 * that is not part of the cycle and make all functions in cycle
 * members of that cycle (top caller == caller with smallest
 * depth-first number).
 */
static void
DEFUN(find_cycle, (child), Sym *child)
{
    Sym *head = 0;
    Sym *tail;
    int cycle_top;
    int index;

    for (cycle_top = dfn_depth; cycle_top > 0; --cycle_top) {
	head = dfn_stack[cycle_top].sym;
	if (child == head) {
	    break;
	} /* if */
	if (child->cg.cyc.head != child && child->cg.cyc.head == head) {
	    break;
	} /* if */
    } /* for */
    if (cycle_top <= 0) {
	fprintf(stderr, "[find_cycle] couldn't find head of cycle\n");
	done(1);
    } /* if */
    DBG(DFNDEBUG, printf("[find_cycle] dfn_depth %d cycle_top %d ",
			 dfn_depth, cycle_top);
	if (head) {
	    print_name(head);
	} else {
	    printf("<unknown>");
	} /* if */
	printf("\n"));
    if (cycle_top == dfn_depth) {
	/*
	 * This is previous function, e.g. this calls itself.  Sort of
	 * boring.
	 *
	 * Since we are taking out self-cycles elsewhere no need for
	 * the special case, here.
	 */
	DBG(DFNDEBUG,
	    printf("[find_cycle] "); print_name(child); printf("\n"));
    } else {
	/*
	 * Glom intervening functions that aren't already glommed into
	 * this cycle.  Things have been glommed when their cyclehead
	 * field points to the head of the cycle they are glommed
	 * into.
	 */
	for (tail = head; tail->cg.cyc.next; tail = tail->cg.cyc.next) {
	    /* void: chase down to tail of things already glommed */
	    DBG(DFNDEBUG,
		printf("[find_cycle] tail "); print_name(tail); printf("\n"));
	} /* for */
	/*
	 * If what we think is the top of the cycle has a cyclehead
	 * field, then it's not really the head of the cycle, which is
	 * really what we want.
	 */
	if (head->cg.cyc.head != head) {
	    head = head->cg.cyc.head;
	    DBG(DFNDEBUG, printf("[find_cycle] new cyclehead ");
		print_name(head); printf("\n"));
	} /* if */
	for (index = cycle_top + 1; index <= dfn_depth; ++index) {
	    child = dfn_stack[index].sym;
	    if (child->cg.cyc.head == child) {
		/*
		 * Not yet glommed anywhere, glom it and fix any
		 * children it has glommed.
		 */
		tail->cg.cyc.next = child;
		child->cg.cyc.head = head;
		DBG(DFNDEBUG, printf("[find_cycle] glomming ");
		    print_name(child); printf(" onto "); print_name(head);
		    printf("\n"));
		for (tail = child; tail->cg.cyc.next; tail = tail->cg.cyc.next)
		{
		    tail->cg.cyc.next->cg.cyc.head = head;
		    DBG(DFNDEBUG, printf("[find_cycle] and its tail ");
			print_name(tail->cg.cyc.next); printf(" onto ");
			print_name(head); printf("\n"));
		} /* for */
	    } else if (child->cg.cyc.head != head /* firewall */) {
		fprintf(stderr, "[find_cycle] glommed, but not to head\n");
		done(1);
	    } /* if */
	} /* for */
    } /* if */
} /* find_cycle */


/*
 * Prepare for visiting the children of PARENT.  Push a parent onto
 * the stack and mark it busy.
 */
static void
DEFUN(pre_visit, (parent), Sym *parent)
{
    ++dfn_depth;
    if (dfn_depth >= DFN_DEPTH) {
	fprintf(stderr, "[pre_visit] dfn_stack overflow\n");
	done(1);
    } /* if */
    dfn_stack[dfn_depth].sym = parent;
    dfn_stack[dfn_depth].cycle_top = dfn_depth;
    parent->cg.top_order = DFN_BUSY;
    DBG(DFNDEBUG, printf("[pre_visit]\t\t%d:", dfn_depth); print_name(parent);
	printf("\n"));
} /* pre_visit */


/*
 * Done with visiting node PARENT.  Pop PARENT off dfn_stack
 * and number functions if PARENT is head of a cycle.
 */
static void
DEFUN(post_visit, (parent), Sym *parent)
{
    Sym *member;

    DBG(DFNDEBUG, printf("[post_visit]\t%d: ", dfn_depth);
	print_name(parent); printf("\n"));
    /*
     * Number functions and things in their cycles unless the function
     * is itself part of a cycle:
     */
    if (parent->cg.cyc.head == parent) {
	++dfn_counter;
	for (member = parent; member; member = member->cg.cyc.next) {
	    member->cg.top_order = dfn_counter;
	    DBG(DFNDEBUG, printf("[post_visit]\t\tmember ");
		print_name(member);
		printf("-> cg.top_order = %d\n", dfn_counter));
	} /* for */
    } else {
	DBG(DFNDEBUG, printf("[post_visit]\t\tis part of a cycle\n"));
    } /* if */
    --dfn_depth;
} /* post_visit */


/*
 * Given this PARENT, depth first number its children.
 */
void
DEFUN(cg_dfn, (parent), Sym *parent)
{
    Arc *arc;

    DBG(DFNDEBUG, printf("[dfn] dfn( "); print_name(parent); printf(")\n"));
    /*
     * If we're already numbered, no need to look any further:
     */
    if (is_numbered(parent)) {
	return;
    } /* if */
    /*
     * If we're already busy, must be a cycle:
     */
    if (is_busy(parent)) {
	find_cycle(parent);
	return;
    } /* if */
    pre_visit(parent);
    /*
     * Recursively visit children:
     */
    for (arc = parent->cg.children; arc; arc = arc->next_child) {
	cg_dfn(arc->child);
    } /* for */
    post_visit(parent);
} /* cg_dfn */

			/*** end of cg_dfn.c ***/
Commit	Line	Data
5489fcc3 KR	1	/*
	2	* Copyright (c) 1983 Regents of the University of California.
	3	* All rights reserved.
	4	*
	5	* Redistribution and use in source and binary forms are permitted
	6	* provided that: (1) source distributions retain this entire copyright
	7	* notice and comment, and (2) distributions including binaries display
	8	* the following acknowledgement: ``This product includes software
	9	* developed by the University of California, Berkeley and its contributors''
	10	* in the documentation or other materials provided with the distribution
	11	* and in all advertising materials mentioning features or use of this
	12	* software. Neither the name of the University nor the names of its
	13	* contributors may be used to endorse or promote products derived
	14	* from this software without specific prior written permission.
	15	* THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
	16	* IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
	17	* WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
	18	*/
	19	#include <stdio.h>
	20	#include "gprof.h"
	21	#include "cg_arcs.h"
	22	#include "cg_dfn.h"
	23	#include "symtab.h"
	24	#include "utils.h"
	25
	26	#define DFN_DEPTH 100
	27
	28	typedef struct {
	29	Sym *sym;
	30	int cycle_top;
	31	} DFN_Stack;
	32
	33	DFN_Stack dfn_stack[DFN_DEPTH];
	34	int dfn_depth = 0;
	35	int dfn_counter = DFN_NAN;
	36
	37
	38	/*
	39	* Is CHILD already numbered?
	40	*/
	41	static bool
	42	DEFUN(is_numbered, (child), Sym *child)
	43	{
	44	return child->cg.top_order != DFN_NAN && child->cg.top_order != DFN_BUSY;
	45	} /* is_numbered */
	46
	47
	48	/*
	49	* Is CHILD already busy?
	50	*/
	51	static bool
	52	DEFUN(is_busy, (child), Sym *child)
	53	{
	54	if (child->cg.top_order == DFN_NAN) {
	55	return FALSE;
	56	} /* if */
	57	return TRUE;
	58	} /* is_busy */
	59
	60
	61	/*
	62	* CHILD is part of a cycle. Find the top caller into this cycle
	63	* that is not part of the cycle and make all functions in cycle
	64	* members of that cycle (top caller == caller with smallest
65	* depth-first number).
66	*/
67	static void
68	DEFUN(find_cycle, (child), Sym *child)
69	{
70	Sym *head = 0;
71	Sym *tail;
72	int cycle_top;
73	int index;
74
75	for (cycle_top = dfn_depth; cycle_top > 0; --cycle_top) {
76	head = dfn_stack[cycle_top].sym;
77	if (child == head) {
78	break;
79	} /* if */
80	if (child->cg.cyc.head != child && child->cg.cyc.head == head) {
81	break;
82	} /* if */
83	} /* for */
84	if (cycle_top <= 0) {
85	fprintf(stderr, "[find_cycle] couldn't find head of cycle\n");
86	done(1);
87	} /* if */
88	DBG(DFNDEBUG, printf("[find_cycle] dfn_depth %d cycle_top %d ",
89	dfn_depth, cycle_top);
90	if (head) {
91	print_name(head);
92	} else {
93	printf("<unknown>");
94	} /* if */
95	printf("\n"));
96	if (cycle_top == dfn_depth) {
97	/*
98	* This is previous function, e.g. this calls itself. Sort of
99	* boring.
100	*
101	* Since we are taking out self-cycles elsewhere no need for
102	* the special case, here.
103	*/
104	DBG(DFNDEBUG,
105	printf("[find_cycle] "); print_name(child); printf("\n"));
106	} else {
107	/*
108	* Glom intervening functions that aren't already glommed into
109	* this cycle. Things have been glommed when their cyclehead
110	* field points to the head of the cycle they are glommed
111	* into.
112	*/
113	for (tail = head; tail->cg.cyc.next; tail = tail->cg.cyc.next) {
114	/* void: chase down to tail of things already glommed */
115	DBG(DFNDEBUG,
116	printf("[find_cycle] tail "); print_name(tail); printf("\n"));
117	} /* for */
118	/*
119	* If what we think is the top of the cycle has a cyclehead
120	* field, then it's not really the head of the cycle, which is
121	* really what we want.
122	*/
123	if (head->cg.cyc.head != head) {
124	head = head->cg.cyc.head;
125	DBG(DFNDEBUG, printf("[find_cycle] new cyclehead ");
126	print_name(head); printf("\n"));
127	} /* if */
128	for (index = cycle_top + 1; index <= dfn_depth; ++index) {
129	child = dfn_stack[index].sym;
130	if (child->cg.cyc.head == child) {
131	/*
132	* Not yet glommed anywhere, glom it and fix any
133	* children it has glommed.
134	*/
135	tail->cg.cyc.next = child;
136	child->cg.cyc.head = head;
137	DBG(DFNDEBUG, printf("[find_cycle] glomming ");
138	print_name(child); printf(" onto "); print_name(head);
139	printf("\n"));
140	for (tail = child; tail->cg.cyc.next; tail = tail->cg.cyc.next)
141	{
142	tail->cg.cyc.next->cg.cyc.head = head;
143	DBG(DFNDEBUG, printf("[find_cycle] and its tail ");
144	print_name(tail->cg.cyc.next); printf(" onto ");
145	print_name(head); printf("\n"));
146	} /* for */
147	} else if (child->cg.cyc.head != head /* firewall */) {
148	fprintf(stderr, "[find_cycle] glommed, but not to head\n");
149	done(1);
150	} /* if */
151	} /* for */
152	} /* if */
153	} /* find_cycle */
154
155
156	/*
157	* Prepare for visiting the children of PARENT. Push a parent onto
158	* the stack and mark it busy.
159	*/
160	static void
161	DEFUN(pre_visit, (parent), Sym *parent)
162	{
163	++dfn_depth;
164	if (dfn_depth >= DFN_DEPTH) {
165	fprintf(stderr, "[pre_visit] dfn_stack overflow\n");
166	done(1);
167	} /* if */
168	dfn_stack[dfn_depth].sym = parent;
169	dfn_stack[dfn_depth].cycle_top = dfn_depth;
170	parent->cg.top_order = DFN_BUSY;
171	DBG(DFNDEBUG, printf("[pre_visit]\t\t%d:", dfn_depth); print_name(parent);
172	printf("\n"));
173	} /* pre_visit */
174
175
176	/*
177	* Done with visiting node PARENT. Pop PARENT off dfn_stack
178	* and number functions if PARENT is head of a cycle.
179	*/
180	static void
181	DEFUN(post_visit, (parent), Sym *parent)
182	{
183	Sym *member;
184
185	DBG(DFNDEBUG, printf("[post_visit]\t%d: ", dfn_depth);
186	print_name(parent); printf("\n"));
187	/*
188	* Number functions and things in their cycles unless the function
189	* is itself part of a cycle:
190	*/
191	if (parent->cg.cyc.head == parent) {
192	++dfn_counter;
193	for (member = parent; member; member = member->cg.cyc.next) {
194	member->cg.top_order = dfn_counter;
195	DBG(DFNDEBUG, printf("[post_visit]\t\tmember ");
196	print_name(member);
197	printf("-> cg.top_order = %d\n", dfn_counter));
198	} /* for */
199	} else {
200	DBG(DFNDEBUG, printf("[post_visit]\t\tis part of a cycle\n"));
201	} /* if */
202	--dfn_depth;
203	} /* post_visit */
204
205
206	/*
207	* Given this PARENT, depth first number its children.
208	*/
209	void
210	DEFUN(cg_dfn, (parent), Sym *parent)
211	{
212	Arc *arc;
213
214	DBG(DFNDEBUG, printf("[dfn] dfn( "); print_name(parent); printf(")\n"));
215	/*
216	* If we're already numbered, no need to look any further:
217	*/
218	if (is_numbered(parent)) {
219	return;
220	} /* if */
221	/*
222	* If we're already busy, must be a cycle:
223	*/
224	if (is_busy(parent)) {
225	find_cycle(parent);
226	return;
227	} /* if */
228	pre_visit(parent);
229	/*
230	* Recursively visit children:
231	*/
232	for (arc = parent->cg.children; arc; arc = arc->next_child) {
233	cg_dfn(arc->child);
234	} /* for */
235	post_visit(parent);
236	} /* cg_dfn */
237
238	/* end of cg_dfn.c */