mpgraph.c

早期freebsd实现

/*	mpgraph.c 1.5 10/12/90 15:57:57	*/
/*	Copyright (c) 1987, Benjamin G. Zorn */

#include	<stdio.h>
#include	"mprof.h"

typedef struct entry {
    char *key;			/* assume keys are character strings */
    char *data;
} ENTRY;

typedef enum {
    FIND,
    ENTER
} ACTION;

void	henter();
ENTRY	*hsearch();

#define	min(i1, i2)		(((i1) < (i2)) ? (i1) : (i2))

#define	UNDEFINED	-1
#define	UNUSED		-1
#define	USED		0

FILE	*stout = stdout;
FILE	*sterr = stderr;

extern	mpcell	hmem[];
extern	char	*strdup();
char	*percent_string();
char	*new_cycle_name();
mpdata	add_data_over();

int	sum_vertex_incoming_calls();
int	sum_vertex_outgoing_calls();

void	print_dynamic_graph_header();
void	print_separator();
void	print_cycle_information();
void	print_vertex_in_cycle();
void	print_normal_vertex();
void	print_self_line();

int	vdata_compar();
int	vbytes_compar();

void	print_vertex();
void	print_edge();
void	print_vecons();

int	v_count;
int	e_count;

struct vecons_struct;

typedef struct vertex_struct {
    char	*name;
    int		number;
    int		srefs;
    mpdata	data;
    struct vecons_struct	*edges;
    struct vecons_struct	*backedges;
    int		*other;
    int		*save;
    int		*scratch;
    struct vertex_struct 	*save_copy;
    /*
     * For SCC detection
     */
    struct vertex_struct 	*father;
    int		k, L;
    bool	on_S;
    /*
     * For SCC representation.
     */
    struct vecons_struct	*scc_members;
    struct vertex_struct 	*in_cycle;
    /*
     * For printing out.
     */
    int		index;
} *vertex, vertex_item;

vertex
make_vertex(name, number, data, scratch)
char	*name;
int	number;
mpdata	data;
int	*scratch;
{
    vertex result = (vertex) malloc(sizeof(vertex_item));
    result->name = name;
    result->number = number;
    result->srefs = 0;
    result->data = data;
    result->backedges = NULL;
    result->edges = NULL;
    result->scratch = scratch;
    result->save_copy = NULL;
    result->father = (vertex) UNDEFINED;
    result->k = 0;
    result->L = 0;
    result->on_S = FALSE;
    result->scc_members = NULL;
    result->in_cycle = NULL;
    result->index = 0;
    henter(name, result);
    return result;
}
    

typedef struct edge_struct {
    vertex	from, to;
    mpdata	data;
    int		mark;
    struct edge_struct *save
} *edge, edge_item;

edge
make_edge(vfrom, vto, data)
vertex	vfrom, vto;
mpdata		data;
{
    edge result = (edge) malloc(sizeof(edge_item));
    result->from = vfrom;
    result->to = vto;
    result->data = data;
    result->mark = UNUSED;
    return result;
}
    

typedef enum { VERTEX, EDGE, VECONS } vetype;

typedef struct	vecons_struct {
    vetype		headtype;
    int			 *vehead;
    struct vecons_struct *vetail;
} vecell_item, *vecell;

#define	VECELL_SIZE	(sizeof(vecell_item))

#define	vehdtype(i)	((i)->headtype)
#define	vehd(i)		((i)->vehead)
#define	vetl(i)		((i)->vetail)
#define	venull(i)	(((char *) i) == NULL)

vecell
vecons(headtype, head, tail)
vetype	headtype;
int	*head;
vecell	tail;
{
    vecell result = (vecell) malloc(VECELL_SIZE);
    vehdtype(result) = headtype;
    vehd(result) = head;
    vetl(result) = tail;
    return result;
}

#define	ccons(h, t)	vecons(VECONS, (int *) (h), (t))
#define	econs(h, t)	vecons(EDGE, (int *) (h), (t))
#define	vcons(h, t)	vecons(VERTEX, (int *) (h), (t))
#define	epush(item, listvar) \
  (listvar = (vecons(EDGE, (int *) (item), listvar)))
#define	vpush(item, listvar) \
  (listvar = (vecons(VERTEX, (int *) (item), listvar)))
#define	cpush(item, listvar) \
  (listvar = (vecons(VECONS, (int *) (item), listvar)))

#define DO_VLIST(var, list) \
	{vertex var; vecell TMPlisttail; \
	   for(TMPlisttail = (list); \
	       !venull(TMPlisttail); \
	       TMPlisttail = vetl(TMPlisttail)) { \
	     var = (vertex) vehd(TMPlisttail); {
#define DO_ELIST(var, list) \
	{edge var; vecell TMPlisttail; \
	   for(TMPlisttail = (list); \
	       !venull(TMPlisttail); \
	       TMPlisttail = vetl(TMPlisttail)) { \
	     var = (edge) vehd(TMPlisttail); {
#define DO_LIST(var, list) \
	{vecell var; vecell TMPlisttail; \
	   for(TMPlisttail = (list); \
	       !venull(TMPlisttail); \
	       TMPlisttail = vetl(TMPlisttail)) { \
	     var = (vecell) vehd(TMPlisttail); {
#define	END_DO }}}

vecell	vsort();	

void
print_vecons(f, cell)
FILE	*f;
vecell	cell;
{
    vecell	rest = cell;

    if (venull(cell)) {
	fprintf(f, "[]");
	return;
    }
	
    fprintf(f, "[");
    do {
	/*
	 * Print the car
	 */
	if (vehdtype(cell) == EDGE) {
	    print_edge(f, (edge) vehd(rest));
	} else if (vehdtype(cell) == VERTEX) {
	    print_vertex(f, (vertex) vehd(rest));
	} else if (vehdtype(cell) == VECONS) {
	    print_vecons(f, (vecell) vehd(rest));
	}
	/*
	 * Check the cdr.
	 */
	if (venull(vetl(rest))) {
	    fprintf(f, "]");
	} else {
	    fprintf(f, " ");
	}
	rest = vetl(rest);
    } while (!venull(rest));
}

int
velength(vel)
vecell	vel;
{
    int		count = 0;
    while (!venull(vel)) {
	count += 1;
	vel = (vecell) vetl(vel);
    }
    return count;
}

vecell
vereverse(vel)
vecell	vel;
{
    vecell	newl = NULL;
    while (!venull(vel)) {
	vpush((vertex) vehd(vel), newl);
	vel = (vecell) vetl(vel);
    }
    return newl;
}

void
print_vertex(f, v)
FILE	*f;
vertex	v;
{
    fprintf(f, "#v(%s :out (", v->name);
    DO_ELIST(e, v->edges)
	fprintf(f, "%s ", e->to->name);
    END_DO
    fprintf(f, ") :in (");
    DO_ELIST(e, v->backedges)
	fprintf(f, "%s ", e->from->name);
    END_DO
    fprintf(f, ")\n");
    
/*    mp_sprint_data(v->data) */
/*  fprintf(f, "edges:");
    print_vecons(f, v->edges);
    fprintf(f, "backedges:");
    print_vecons(f, v->backedges);
*/
    fflush(f);
}

void
print_edge(f, e)
FILE	*f;
edge	e;
{
    fprintf(f, "#e(%s %s)\n", e->from->name, e->to->name);
    fprintf(f, "%s\n", mp_sprint_data(e->data));
    fflush(f);
}



typedef struct graph_struct {
    int		v_count;
    vecell	vset;
    int		e_count;
    vecell	eset;
    struct graph_struct	*derived;
} *graph, graph_item;

graph	read_graph();
graph	merge_scc();

graph
make_graph(v_count, vset, e_count, eset)
int	v_count;
vecell	vset;
int	e_count;
vecell	eset;
{
    graph result = (graph) malloc(sizeof(graph_item));
    result->v_count = v_count;
    result->vset = vset;
    result->e_count = e_count;
    result->eset = eset;
    result->derived = NULL;
    return result;
}

void
print_graph(f, g)
FILE	*f;
graph	g;
{
    fprintf(f, "#g(vc:%d ", g->v_count);
    print_vecons(f, g->vset);
    fprintf(f, "\nec:%d ", g->e_count);
    print_vecons(f, g->eset);
    fprintf(f, ")\n");
    fflush(f);
}


/*
 * copy_graph -- basically, we have to copy all the vertices and edges
 * from the old graph structure.
 */

void
free_graph(g)
graph	g;
{
    vecell	rest, tmp;

    for (rest = g->vset; !venull(rest);) {
	tmp = rest;
	rest = vetl(rest);
	free((char *) vehd(tmp));
	free(tmp);
    }
    for (rest = g->eset; !venull(rest);) {
	tmp = rest;
	rest = vetl(rest);
	free((char *) vehd(tmp));
	free(tmp);
    }
    free(g);
}

/*
 * copy_graph -- basically, we have to copy all the vertices and edges
 * from the old graph structure.
 */

graph
copy_graph(g)
graph	g;
{
    vecell	new_vset = NULL, new_eset = NULL;
    vertex	new_v;
    edge	new_e;
    graph	newg = make_graph(g->v_count, g->vset, g->e_count, g->eset);

    DO_VLIST (v, g->vset)
        new_v = make_vertex(v->name, v->number, v->data, v->scratch);
        v->save_copy = new_v;
	vpush(new_v, new_vset);
    END_DO

    DO_ELIST (e, g->eset)
        mpdata	newdata = mp_new_data();
	vertex	old_vfrom, old_vto;
    
        newdata = mp_add_data(newdata, e->data);
	old_vfrom = e->from;
	old_vto = e->to;
	new_e = make_edge(old_vfrom->save_copy, old_vto->save_copy, newdata);
	epush(new_e, ((new_e->from)->edges));
	epush(new_e, ((new_e->to)->backedges));
	epush(new_e, new_eset);
    END_DO
      
    DO_VLIST (v, g->vset)
        v->save_copy = NULL;
    END_DO
      
    newg->vset = new_vset;
    newg->eset = new_eset;
    newg->derived = g;
    return newg;
}
        
    
vecell	scc();


/*
 * Hash routines -- specialized from on routines available in SunOS
 * and Ultrix libraries, but not in Berkeley Unix.
 */

ENTRY	*htable;
int	htableSize = 0;

int
hcreate(tableSize)
unsigned tableSize;
{
    htableSize = tableSize;
    htable = (ENTRY *) calloc(tableSize, sizeof(ENTRY));
    if (htable == NULL) return 0;
    return 1;
}

void
hdestroy()
{
    free(htable);
}

int
hash_fn(str, tableSize)
char	*str;
int	tableSize;
{
    int		i;
    int		result = 12345;
    
    for (i = 0; i < strlen(str); i++) {
	result =  ((result + ((int) str[i]) * 1013) & 0x7ffffff) >> 3;
    }
    return (result % tableSize);
}

ENTRY *
hsearch(item, action)
ENTRY	item;
ACTION	action;
{
    int		i, hindex;
    int		hvalue = hash_fn(item.key, htableSize);
    
    for (i = 0; i < htableSize; i++) {
	hindex = ((i + hvalue) % htableSize);
	if (htable[hindex].key == 0) {
	    /*
	     * Won't find the item.
	     */
	    if (action == ENTER) {
		htable[hindex] = item;
		return &(htable[hindex]);
	    } else {
		return NULL;
	    }
	} else if (strcmp(htable[hindex].key, item.key) == 0) {
	    /*
	     * Found the item in the table.
	     */
	    if (action == ENTER) {
		htable[hindex] = item;
	    }
	    return &(htable[hindex]);
	}
    }
    /*
     * We won't find the item.
     */
    return NULL;
}    

void
henter(key, vp)
char	*key;
vertex	vp;
{
    ENTRY	e;
    e.key = key;
    e.data = (char *) vp;
    (void) hsearch(e, ENTER);
}

vertex
hlookup(key)
char	*key;
{
    ENTRY	e, *result;
    e.key = key;
    
    result = hsearch(e, FIND);
    return (vertex) result->data;
}


#define template0 \
  "\n---------------------------s--m--l--x-------------------s--m--l--x---------------\n\n"
#define template1 \
  "  %8s %12s |%-12s | %12s |%-12s | %12s   %-s\n"
#define template1n \
  "  %8s %12d |%-12s | %12d |%-12s | %12d   %-s\n"
#define template1f \
  "  %8.1f %12d |%-12s | %12d |%-12s | %12d   %-s\n"

#define template2 \
  "%-5s%7s%9s %-5s |%-12s |%-12s |%8s%-9s%-s\n"
  
#define template2p1 \
  "%-5s%7s%9d %-5s |%-12s |%-12s |%8s%-9s%-s\n"
#define template2p2 \
  "%-5s%7s%9d %-5s |%-12s |%-12s |%8d%-9s%-s\n"

#define template2c1 \
  "%-5s%7s%9s %-5s |%-12s |%-12s |%8d%-9s%-s\n"

double
dpercent(x, y)
int	x, y;
{
    if (y == 0) {
	return 0;
    } else {
	return (100.0 * x) / y;
    }
}

char *
truncate_or_blank(d)
double	d;
{
    char	cbuf[80];
    int		intpart = d;
    double	fraction = d - intpart;
    if ((intpart == 0) && (fraction < 0.00001)) {
	return "";
    } else if (intpart == 0) {
	return ".";
    } else if (intpart == 100) {
	return "**";
    } else {
	sprintf(cbuf, "%2d", intpart);
	return strdup(cbuf);
    }
}
	

char *
data_type_string(d, divisor)
mpdata	d;
int	divisor;
{
    char	cbuf[100];
    
    if (divisor == 0) {
	return "";
    } else {
	sprintf(cbuf, " %2s %2s %2s %2s",
		truncate_or_blank(dpercent(dt_b_small(d), divisor)),
		truncate_or_blank(dpercent(dt_b_med(d), divisor)),
		truncate_or_blank(dpercent(dt_b_large(d), divisor)),
		truncate_or_blank(dpercent(dt_b_xlarge(d), divisor)));
	return strdup(cbuf);
    }
}

char *
data_kept_string(d, divisor)
mpdata	d;
int	divisor;
{
    char	cbuf[100];
    
    if (divisor == 0) {
	return "";
    } else {
	sprintf(cbuf, " %2s %2s %2s %2s",
		truncate_or_blank(dpercent(dt_d_small(d), divisor)),
		truncate_or_blank(dpercent(dt_d_med(d), divisor)),
		truncate_or_blank(dpercent(dt_d_large(d), divisor)),
		truncate_or_blank(dpercent(dt_d_xlarge(d), divisor)));
	return strdup(cbuf);
    }
}

char *
relative_type_string(num, den)
mpdata	num, den;
{
    return data_type_string(num, mp_sum_data(den));
}

char *
relative_kept_string(num, den)
mpdata	num, den;
{
    return data_kept_string(num, mp_sum_kept(den));
}

char *
type_fraction_string(d)
mpdata	d;
{
    return data_type_string(d, mp_sum_data(d));
}
		
char
 *
kept_fraction_string(d)
mpdata	d;
{
    return data_kept_string(d, mp_sum_kept(d));
}

int
sum_data_over_edges(elist)
vecell	elist;
{
    int		sum = 0;
    
    DO_ELIST(e, elist)
	if (!((e->to->in_cycle != NULL) ||
	      (e->from->in_cycle != NULL))) {
	    sum += mp_sum_data(e->data);
	}
    END_DO
    return sum;
}

int
sum_calls_over_edges(elist)
vecell	elist;
{
    int		sum = 0;
    
    DO_ELIST(e, elist)
	if (!((e->to->in_cycle != NULL) ||
	      (e->from->in_cycle != NULL))) {
	    sum += mp_sum_calls(e->data);
	}
    END_DO
    return sum;
}

int
sum_vertex_bytes(v)
vertex	v;
{
    if (v->in_cycle == NULL) {
	return mp_sum_data(v->data) + sum_data_over_edges(v->edges);
    } else {
	return sum_vertex_bytes(v->in_cycle);
    }
}

int
sum_vertex_bytes1(v)
vertex	v;
{
    if (v->in_cycle == NULL) {
	return mp_sum_data(v->data) + sum_data_over_edges(v->edges);
    } else {
	return mp_sum_data(v->data);
    }
}

int
sum_vertex_incoming_calls(v)
vertex	v;
{
    if (v->in_cycle == NULL) {
	return sum_calls_over_edges(v->backedges);
    } else {
	return sum_vertex_incoming_calls(v->in_cycle);
    }
}

int
sum_vertex_outgoing_calls(v)
vertex	v;
{
    if (v->in_cycle == NULL) {
	return sum_calls_over_edges(v->edges);
    } else {
	return sum_vertex_outgoing_calls(v->in_cycle);
    }
}

void
mprof_graph_ops(f)
FILE	*f;
{
    graph	g = read_graph();
    graph	newg = merge_scc(g);
    int		cumul_bytes;
    int		total_bytes;
    int		total_calls;
    int		total_kept;
    mpdata	total_data = mp_new_data();
    vecell	old_vset = g->vset;
    vecell	vset = newg->vset;
    vecell	ordered_vset = NULL;
    vecell	old_ordered_vset;
    int		i;

    old_ordered_vset = vsort(old_vset, vdata_compar);
    
    DO_VLIST (v, old_vset)
	total_data = mp_add_data(total_data, v->data);
    END_DO

    total_bytes = mp_sum_data(total_data);
    total_calls = mp_sum_calls(total_data);
    total_kept = mp_sum_kept(total_data);

    /*
     * Print out the allocation recorded in the leaf nodes.
     */
    fprintf(f, "---------  Direct Allocation Table ------------\n\n");
    fprintf(f, template1,
	    " % mem",
	    "bytes",
	    " % mem(size)",
	    "bytes kept",
	    "  % all kept",
	    "calls",
	    "name");
    fprintf(f, template0);
    fprintf(f, template1n,
	    "-----",
	    total_bytes,
	    type_fraction_string(total_data),
	    total_kept,
	    kept_fraction_string(total_data),
	    total_calls,
	    "<TOTAL>");
    fprintf(f, "\n");
    DO_VLIST(v, old_ordered_vset)
	mpdata	vdata = v->data;
	int	nbytes = mp_sum_data(vdata);
	if (nbytes != 0) {
	    cumul_bytes += nbytes;
	    fprintf(f, template1f,
		    dpercent(nbytes, total_bytes),
		    nbytes,
		    relative_type_string(vdata, total_data),
		    mp_sum_kept(vdata),
		    data_kept_string(vdata, total_kept),
		    mp_sum_calls(vdata),
		    v->name);
	}
    END_DO

    /*
     * Check allocation consistency from children to parents.
     */

    DO_VLIST(v, vereverse(vset))
	/*
	 * Because the vertex list is sorted, we always encounter a
	 * node before any of the callers of that node and after all
	 * the nodes it calls.
	 */
        vecell	clist = v->edges;
        vecell	plist = v->backedges;
        int	csum = sum_data_over_edges(clist);
        int	psum = sum_data_over_edges(plist);

        if (!(v->in_cycle) &&
	    (v->backedges != NULL) &&
	    (psum != (csum + mp_sum_data(v->data)))) {
	    fprintf(f, "Parent and child disagree on data allocation\n");
	    fprintf(f, "%s --> %d != %d + %d (%d)\n",
		    v->name, psum, csum, csum + mp_sum_data(v->data));
	}
    END_DO

    ordered_vset = vsort(vset, vbytes_compar);
    i = 0;
    DO_VLIST(v, ordered_vset)
	v->index = i;
	i += 1;
    END_DO

    /*
     * Print the header for the dynamic allocation graph.
     */
    print_dynamic_graph_header(f);