- Support inlined location in calltree output.

  In case of multiple level of inlining all the locations are flattened.
  Require recent binutils/addr2line (head works or binutils from ports
  with the right $PATH order).
- Multiple fixes in the calltree output (recursion case, ...)
- Fix the calltree top view that previously hide some shared nodes.

Tested with Kcachegrind(kdesdk4)/qcachegrind(head).

Sponsored by: NETASQ

2 files changed, 402 insertions, 241 deletions

diff --git a/usr.sbin/pmcstat/pmcpl_calltree.c b/usr.sbin/pmcstat/pmcpl_calltree.c
index 0069330..6b8bc61 100644
--- a/usr.sbin/pmcstat/pmcpl_calltree.c
+++ b/usr.sbin/pmcstat/pmcpl_calltree.c
@@ -1,5 +1,5 @@
 /*-
- * Copyright (c) 2009, Fabien Thomas
+ * Copyright (c) 2012, Fabien Thomas
  * All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
@@ -58,20 +58,18 @@ __FBSDID("$FreeBSD$");
 #include "pmcstat_top.h"
 #include "pmcpl_calltree.h"
 
-#define PMCPL_CT_GROWSIZE	4
-
-static pmcstat_interned_string pmcpl_ct_prevfn;
+#define	PMCPL_CT_GROWSIZE	4
 
 static int pmcstat_skiplink = 0;
 
 struct pmcpl_ct_node;
 
 /* Get the sample value for PMC a. */
-#define PMCPL_CT_SAMPLE(a, b) \
+#define	PMCPL_CT_SAMPLE(a, b) \
 	((a) < (b)->npmcs ? (b)->sb[a] : 0)
 
 /* Get the sample value in percent related to rsamples. */
-#define PMCPL_CT_SAMPLEP(a, b) \
+#define	PMCPL_CT_SAMPLEP(a, b) \
 	(PMCPL_CT_SAMPLE(a, b) * 100.0 / rsamples->sb[a])
 
 struct pmcpl_ct_sample {
@@ -95,10 +93,13 @@ struct pmcpl_ct_instr {
  * Each calltree node is tracked by a pmcpl_ct_node struct.
  */
 struct pmcpl_ct_node {
-#define PMCPL_PCT_TAG	0x00000001	/* Loop detection. */
-	uint32_t		pct_flags;
 	struct pmcstat_image	*pct_image;
 	uintfptr_t		pct_func;
+
+	struct pmcstat_symbol	*pct_sym;
+	pmcstat_interned_string	pct_ifl;
+	pmcstat_interned_string	pct_ifn;
+
 	struct pmcpl_ct_sample	pct_samples;
 
 	int			pct_narc;
@@ -109,17 +110,25 @@ struct pmcpl_ct_node {
 	int			pct_ninstr;
 	int			pct_instr_c;
 	struct pmcpl_ct_instr	*pct_instr;
+
+#define PMCPL_PCT_ADDR	0
+#define PMCPL_PCT_NAME	1
+	char			pct_type;
+#define	PMCPL_PCT_WHITE	0
+#define	PMCPL_PCT_GREY	1
+#define	PMCPL_PCT_BLACK	2
+	char			pct_color;
 };
 
 struct pmcpl_ct_node_hash {
 	struct pmcpl_ct_node  *pch_ctnode;
-	LIST_ENTRY(pmcpl_ct_node_hash) pch_next;
+	STAILQ_ENTRY(pmcpl_ct_node_hash) pch_next;
 };
 
 struct pmcpl_ct_sample pmcpl_ct_callid;
 
-#define PMCPL_CT_MAXCOL		PMC_CALLCHAIN_DEPTH_MAX	
-#define PMCPL_CT_MAXLINE	1024	/* TODO: dynamic. */
+#define	PMCPL_CT_MAXCOL		PMC_CALLCHAIN_DEPTH_MAX
+#define	PMCPL_CT_MAXLINE	1024	/* TODO: dynamic. */
 
 struct pmcpl_ct_line {
 	unsigned	ln_sum;
@@ -127,12 +136,13 @@ struct pmcpl_ct_line {
 };
 
 struct pmcpl_ct_line	pmcpl_ct_topmax[PMCPL_CT_MAXLINE+1];
-struct pmcpl_ct_node	*pmcpl_ct_topscreen[PMCPL_CT_MAXCOL+1][PMCPL_CT_MAXLINE+1];
+struct pmcpl_ct_node
+    *pmcpl_ct_topscreen[PMCPL_CT_MAXCOL+1][PMCPL_CT_MAXLINE+1];
 
 /*
  * All nodes indexed by function/image name are placed in a hash table.
  */
-static LIST_HEAD(,pmcpl_ct_node_hash) pmcpl_ct_node_hash[PMCSTAT_NHASH];
+static STAILQ_HEAD(,pmcpl_ct_node_hash) pmcpl_ct_node_hash[PMCSTAT_NHASH];
 
 /*
  * Root node for the graph.
@@ -256,7 +266,8 @@ pmcpl_ct_instr_grow(int cursize, int *maxsize, struct pmcpl_ct_instr **items)
  */
 
 static void
-pmcpl_ct_instr_add(struct pmcpl_ct_node *ct, int pmcin, uintfptr_t pc)
+pmcpl_ct_instr_add(struct pmcpl_ct_node *ct, int pmcin,
+    uintfptr_t pc, unsigned v)
 {
 	int i;
 	struct pmcpl_ct_instr *in;
@@ -265,7 +276,7 @@ pmcpl_ct_instr_add(struct pmcpl_ct_node *ct, int pmcin, uintfptr_t pc)
 		if (ct->pct_instr[i].pctf_func == pc) {
 			in = &ct->pct_instr[i];
 			pmcpl_ct_samples_grow(&in->pctf_samples);
-			in->pctf_samples.sb[pmcin]++;
+			in->pctf_samples.sb[pmcin] += v;
 			return;
 		}
 	}
@@ -275,7 +286,7 @@ pmcpl_ct_instr_add(struct pmcpl_ct_node *ct, int pmcin, uintfptr_t pc)
 	in->pctf_func = pc;
 	pmcpl_ct_samples_init(&in->pctf_samples);
 	pmcpl_ct_samples_grow(&in->pctf_samples);
-	in->pctf_samples.sb[pmcin] = 1;
+	in->pctf_samples.sb[pmcin] = v;
 	ct->pct_ninstr++;
 }
 
@@ -284,19 +295,19 @@ pmcpl_ct_instr_add(struct pmcpl_ct_node *ct, int pmcin, uintfptr_t pc)
  */
 
 static struct pmcpl_ct_node *
-pmcpl_ct_node_allocate(struct pmcstat_image *image, uintfptr_t pc)
+pmcpl_ct_node_allocate(void)
 {
 	struct pmcpl_ct_node *ct;
 
 	if ((ct = malloc(sizeof(*ct))) == NULL)
 		err(EX_OSERR, "ERROR: Cannot allocate callgraph node");
 
-	ct->pct_flags	= 0;
-	ct->pct_image 	= image;
-	ct->pct_func	= pc;
-
 	pmcpl_ct_samples_init(&ct->pct_samples);
 
+	ct->pct_sym	= NULL;
+	ct->pct_image	= NULL;
+	ct->pct_func	= 0;
+
 	ct->pct_narc	= 0;
 	ct->pct_arc_c	= 0;
 	ct->pct_arc	= NULL;
@@ -305,6 +316,8 @@ pmcpl_ct_node_allocate(struct pmcstat_image *image, uintfptr_t pc)
 	ct->pct_instr_c	= 0;
 	ct->pct_instr	= NULL;
 
+	ct->pct_color   = PMCPL_PCT_WHITE;
+
 	return (ct);
 }
 
@@ -338,10 +351,10 @@ pmcpl_ct_node_cleartag(void)
 	struct pmcpl_ct_node_hash *pch;
 
 	for (i = 0; i < PMCSTAT_NHASH; i++)
-		LIST_FOREACH(pch, &pmcpl_ct_node_hash[i], pch_next)
-			pch->pch_ctnode->pct_flags &= ~PMCPL_PCT_TAG;
+		STAILQ_FOREACH(pch, &pmcpl_ct_node_hash[i], pch_next)
+			pch->pch_ctnode->pct_color = PMCPL_PCT_WHITE;
 
-	pmcpl_ct_root->pct_flags &= ~PMCPL_PCT_TAG;
+	pmcpl_ct_root->pct_color = PMCPL_PCT_WHITE;
 }
 
 /*
@@ -355,11 +368,9 @@ pmcpl_ct_node_dumptop(int pmcin, struct pmcpl_ct_node *ct,
 	int i, terminal;
 	struct pmcpl_ct_arc *arc;
 
-	if (ct->pct_flags & PMCPL_PCT_TAG)
+	if (ct->pct_color == PMCPL_PCT_GREY)
 		return 0;
 
-	ct->pct_flags |= PMCPL_PCT_TAG;
-
 	if (x >= PMCPL_CT_MAXCOL) {
 		pmcpl_ct_topscreen[x][*y] = NULL;
 		return 1;
@@ -374,11 +385,11 @@ pmcpl_ct_node_dumptop(int pmcin, struct pmcpl_ct_node *ct,
 	terminal = 1;
 	for (i = 0; i < ct->pct_narc; i++) {
 		arc = &ct->pct_arc[i];
-		if (PMCPL_CT_SAMPLE(pmcin,
+		if (arc->pcta_child->pct_color != PMCPL_PCT_GREY &&
+		    PMCPL_CT_SAMPLE(pmcin,
 		    &arc->pcta_samples) != 0 &&
 		    PMCPL_CT_SAMPLEP(pmcin,
-		    &arc->pcta_samples) > pmcstat_threshold &&
-		    (arc->pcta_child->pct_flags & PMCPL_PCT_TAG) == 0) {
+		    &arc->pcta_samples) > pmcstat_threshold) {
 			terminal = 0;
 			break;
 		}
@@ -395,6 +406,7 @@ pmcpl_ct_node_dumptop(int pmcin, struct pmcpl_ct_node *ct,
 		return 0;
 	}
 
+	ct->pct_color = PMCPL_PCT_GREY;
 	for (i = 0; i < ct->pct_narc; i++) {
 		if (PMCPL_CT_SAMPLE(pmcin,
 		    &ct->pct_arc[i].pcta_samples) == 0)
@@ -403,10 +415,13 @@ pmcpl_ct_node_dumptop(int pmcin, struct pmcpl_ct_node *ct,
 		    &ct->pct_arc[i].pcta_samples) > pmcstat_threshold) {
 			if (pmcpl_ct_node_dumptop(pmcin,
 			        ct->pct_arc[i].pcta_child,
-			        rsamples, x+1, y))
+			        rsamples, x+1, y)) {
+				ct->pct_color = PMCPL_PCT_BLACK;
 				return 1;
+			}
 		}
 	}
+	ct->pct_color = PMCPL_PCT_BLACK;
 
 	return 0;
 }
@@ -446,7 +461,6 @@ pmcpl_ct_node_printtop(struct pmcpl_ct_sample *rsamples, int pmcin, int maxy)
 	float v;
 	char ns[30], vs[10], is[20];
 	struct pmcpl_ct_node *ct;
-	struct pmcstat_symbol *sym;
 	const char *space = " ";
 
 	/*
@@ -503,10 +517,9 @@ pmcpl_ct_node_printtop(struct pmcpl_ct_sample *rsamples, int pmcin, int maxy)
 				strlcpy(ns, ".", sizeof(ns));
 				ns_len = 1;
 			} else {
-			sym = pmcstat_symbol_search(ct->pct_image, ct->pct_func);
-			if (sym != NULL) {
+			if (ct->pct_sym != NULL) {
 				ns_len = snprintf(ns, sizeof(ns), "%s",
-				    pmcstat_string_unintern(sym->ps_name));
+				    pmcstat_string_unintern(ct->pct_sym->ps_name));
 			} else
 				ns_len = snprintf(ns, sizeof(ns), "%p",
 				    (void *)ct->pct_func);
@@ -547,7 +560,6 @@ pmcpl_ct_topdisplay(void)
 
 	rsamples = &r;
 	pmcpl_ct_samples_root(rsamples);
-
 	pmcpl_ct_node_cleartag();
 
 	PMCSTAT_PRINTW("%5.5s %s\n", "%SAMP", "CALLTREE");
@@ -589,81 +601,92 @@ pmcpl_ct_topkeypress(int c, WINDOW *w)
  * `ppm'.
  */
 
-static struct pmcpl_ct_node *
-pmcpl_ct_node_hash_lookup_pc(struct pmcpl_ct_node *parent,
-    struct pmcstat_pcmap *ppm, uintfptr_t pc, int pmcin)
+static void
+pmcpl_ct_node_update(struct pmcpl_ct_node *parent,
+    struct pmcpl_ct_node *child, int pmcin, unsigned v, int cd)
 {
-	struct pmcstat_symbol *sym;
-	struct pmcstat_image *image;
-	struct pmcpl_ct_node *ct;
-	struct pmcpl_ct_node_hash *h;
 	struct pmcpl_ct_arc *arc;
-	uintfptr_t loadaddress;
 	int i;
-	unsigned int hash;
 
 	assert(parent != NULL);
 
-	image = ppm->ppm_image;
-
-	loadaddress = ppm->ppm_lowpc + image->pi_vaddr - image->pi_start;
-	pc -= loadaddress;	/* Convert to an offset in the image. */
+	/*
+	 * Find related arc in parent node and
+	 * increment the sample count.
+	 */
+	for (i = 0; i < parent->pct_narc; i++) {
+		if (parent->pct_arc[i].pcta_child == child) {
+			arc = &parent->pct_arc[i];
+			pmcpl_ct_samples_grow(&arc->pcta_samples);
+			arc->pcta_samples.sb[pmcin] += v;
+			/* Estimate call count. */
+			if (cd) {
+			pmcpl_ct_samples_grow(&arc->pcta_callid);
+			if (pmcpl_ct_callid.sb[pmcin] -
+			    arc->pcta_callid.sb[pmcin] > 1)
+				arc->pcta_call++;
+			arc->pcta_callid.sb[pmcin] =
+			    pmcpl_ct_callid.sb[pmcin];
+			}
+			return;
+		}
+	}
 
 	/*
-	 * Try determine the function at this offset.  If we can't
-	 * find a function round leave the `pc' value alone.
+	 * No arc found for us, add ourself to the parent.
 	 */
-	if ((sym = pmcstat_symbol_search(image, pc)) != NULL)
-		pc = sym->ps_start;
-	else
-		pmcstat_stats.ps_samples_unknown_function++;
+	pmcpl_ct_arc_grow(parent->pct_narc,
+	    &parent->pct_arc_c, &parent->pct_arc);
+	arc = &parent->pct_arc[parent->pct_narc];
+	pmcpl_ct_samples_grow(&arc->pcta_samples);
+	arc->pcta_samples.sb[pmcin] = v;
+	arc->pcta_call = 1;
+	if (cd) {
+		pmcpl_ct_samples_grow(&arc->pcta_callid);
+		arc->pcta_callid.sb[pmcin] = pmcpl_ct_callid.sb[pmcin];
+	}
+	arc->pcta_child = child;
+	parent->pct_narc++;
+}
+
+/*
+ * Lookup by image/pc.
+ */
+
+static struct pmcpl_ct_node *
+pmcpl_ct_node_hash_lookup(struct pmcstat_image *image, uintfptr_t pc,
+    struct pmcstat_symbol *sym, char *fl, char *fn)
+{
+	int i;
+	unsigned int hash;
+	struct pmcpl_ct_node *ct;
+	struct pmcpl_ct_node_hash *h;
+	pmcstat_interned_string	ifl, ifn;
+
+	if (fn != NULL) {
+		ifl = pmcstat_string_intern(fl);
+		ifn = pmcstat_string_intern(fn);
+	} else {
+		ifl = 0;
+		ifn = 0;
+	}
 
 	for (hash = i = 0; i < (int)sizeof(uintfptr_t); i++)
 		hash += (pc >> i) & 0xFF;
 
 	hash &= PMCSTAT_HASH_MASK;
 
-	ct = NULL;
-	LIST_FOREACH(h, &pmcpl_ct_node_hash[hash], pch_next) {
+	STAILQ_FOREACH(h, &pmcpl_ct_node_hash[hash], pch_next) {
 		ct = h->pch_ctnode;
 
 		assert(ct != NULL);
 
 		if (ct->pct_image == image && ct->pct_func == pc) {
-			/*
-			 * Find related arc in parent node and
-			 * increment the sample count.
-			 */
-			for (i = 0; i < parent->pct_narc; i++) {
-				if (parent->pct_arc[i].pcta_child == ct) {
-					arc = &parent->pct_arc[i];
-					pmcpl_ct_samples_grow(&arc->pcta_samples);
-					arc->pcta_samples.sb[pmcin]++;
-					/* Estimate call count. */
-					pmcpl_ct_samples_grow(&arc->pcta_callid);
-					if (pmcpl_ct_callid.sb[pmcin] -
-					    arc->pcta_callid.sb[pmcin] > 1)
-						arc->pcta_call++;
-					arc->pcta_callid.sb[pmcin] =
-					    pmcpl_ct_callid.sb[pmcin];
-					return (ct);
-				}
-			}
-
-			/*
-			 * No arc found for us, add ourself to the parent.
-			 */
-			pmcpl_ct_arc_grow(parent->pct_narc,
-			    &parent->pct_arc_c, &parent->pct_arc);
-			arc = &parent->pct_arc[parent->pct_narc];
-			pmcpl_ct_samples_grow(&arc->pcta_samples);
-			arc->pcta_samples.sb[pmcin] = 1;
-			arc->pcta_call = 1;
-			pmcpl_ct_samples_grow(&arc->pcta_callid);
-			arc->pcta_callid.sb[pmcin] = pmcpl_ct_callid.sb[pmcin];
-			arc->pcta_child = ct;
-			parent->pct_narc++;
-			return (ct);
+			if (fn == NULL)
+				return (ct);
+			if (ct->pct_type == PMCPL_PCT_NAME &&
+			    ct->pct_ifl == ifl && ct->pct_ifn == ifn)
+				return (ct);
 		}
 	}
 
@@ -671,23 +694,22 @@ pmcpl_ct_node_hash_lookup_pc(struct pmcpl_ct_node *parent,
 	 * We haven't seen this (pmcid, pc) tuple yet, so allocate a
 	 * new callgraph node and a new hash table entry for it.
 	 */
-	ct = pmcpl_ct_node_allocate(image, pc);
+	ct = pmcpl_ct_node_allocate();
 	if ((h = malloc(sizeof(*h))) == NULL)
 		err(EX_OSERR, "ERROR: Could not allocate callgraph node");
 
-	h->pch_ctnode = ct;
-	LIST_INSERT_HEAD(&pmcpl_ct_node_hash[hash], h, pch_next);
+	if (fn != NULL) {
+		ct->pct_type = PMCPL_PCT_NAME;
+		ct->pct_ifl = ifl;
+		ct->pct_ifn = ifn;
+	} else
+		ct->pct_type = PMCPL_PCT_ADDR;
+	ct->pct_image = image;
+	ct->pct_func = pc;
+	ct->pct_sym = sym;
 
-	pmcpl_ct_arc_grow(parent->pct_narc,
-	    &parent->pct_arc_c, &parent->pct_arc);
-	arc = &parent->pct_arc[parent->pct_narc];
-	pmcpl_ct_samples_grow(&arc->pcta_samples);
-	arc->pcta_samples.sb[pmcin] = 1;
-	arc->pcta_call = 1;
-	pmcpl_ct_samples_grow(&arc->pcta_callid);
-	arc->pcta_callid.sb[pmcin] = pmcpl_ct_callid.sb[pmcin];
-	arc->pcta_child = ct;
-	parent->pct_narc++;
+	h->pch_ctnode = ct;
+	STAILQ_INSERT_HEAD(&pmcpl_ct_node_hash[hash], h, pch_next);
 	return (ct);
 }
 
@@ -699,10 +721,14 @@ void
 pmcpl_ct_process(struct pmcstat_process *pp, struct pmcstat_pmcrecord *pmcr,
     uint32_t nsamples, uintfptr_t *cc, int usermode, uint32_t cpu)
 {
-	int n, pmcin;
+	int i, n, pmcin;
+	uintfptr_t pc, loadaddress;
+	struct pmcstat_image *image;
+	struct pmcstat_symbol *sym;
 	struct pmcstat_pcmap *ppm[PMC_CALLCHAIN_DEPTH_MAX];
 	struct pmcstat_process *km;
-	struct pmcpl_ct_node *parent, *child;
+	struct pmcpl_ct_node *ct;
+	struct pmcpl_ct_node *ctl[PMC_CALLCHAIN_DEPTH_MAX+1];
 
 	(void) cpu;
 
@@ -741,30 +767,114 @@ pmcpl_ct_process(struct pmcstat_process *pp, struct pmcstat_pmcrecord *pmcr,
 	pmcpl_ct_callid.sb[pmcin]++;
 
 	/*
-	 * Iterate remaining addresses.
+	 * Build node list.
 	 */
-	for (parent = pmcpl_ct_root, child = NULL; n >= 0; n--) {
-		child = pmcpl_ct_node_hash_lookup_pc(parent, ppm[n], cc[n],
-		    pmcin);
-		if (child == NULL) {
+	ctl[0] = pmcpl_ct_root;
+	for (i = 1; n >= 0; n--) {
+		image = ppm[n]->ppm_image;
+		loadaddress = ppm[n]->ppm_lowpc +
+		    image->pi_vaddr - image->pi_start;
+		/* Convert to an offset in the image. */
+		pc = cc[n] - loadaddress;
+		/*
+		 * Try determine the function at this offset.  If we can't
+		 * find a function round leave the `pc' value alone.
+		 */
+		if ((sym = pmcstat_symbol_search(image, pc)) != NULL)
+			pc = sym->ps_start;
+		else
+			pmcstat_stats.ps_samples_unknown_function++;
+
+		ct = pmcpl_ct_node_hash_lookup(image, pc, sym, NULL, NULL);
+		if (ct == NULL) {
 			pmcstat_stats.ps_callchain_dubious_frames++;
 			continue;
 		}
-		parent = child;
+		ctl[i++] = ct;
 	}
+	/* No valid node found. */
+	if (i == 1)
+		return;
+	n = i;
+
+	ct = ctl[0];
+	for (i = 1; i < n; i++)
+		pmcpl_ct_node_update(ctl[i-1], ctl[i], pmcin, 1, 1);
 
 	/*
 	 * Increment the sample count for this PMC.
 	 */
-	if (child != NULL) {
-		pmcpl_ct_samples_grow(&child->pct_samples);
-		child->pct_samples.sb[pmcin]++;
-
-		/* Update per instruction sample if required. */
-		if (args.pa_ctdumpinstr)
-			pmcpl_ct_instr_add(child, pmcin, cc[0] -
-			    (ppm[0]->ppm_lowpc + ppm[0]->ppm_image->pi_vaddr -
-			     ppm[0]->ppm_image->pi_start));
+	pmcpl_ct_samples_grow(&ctl[n-1]->pct_samples);
+	ctl[n-1]->pct_samples.sb[pmcin]++;
+
+	/* Update per instruction sample if required. */
+	if (args.pa_ctdumpinstr)
+		pmcpl_ct_instr_add(ctl[n-1], pmcin, cc[0] -
+		    (ppm[0]->ppm_lowpc + ppm[0]->ppm_image->pi_vaddr -
+		     ppm[0]->ppm_image->pi_start), 1);
+}
+
+/*
+ * Print node child cost.
+ */
+
+static void
+pmcpl_ct_node_printchild(struct pmcpl_ct_node *ct, uintfptr_t paddr,
+    int pline)
+{
+	int i, j, line;
+	uintfptr_t addr;
+	struct pmcpl_ct_node *child;
+	char sourcefile[PATH_MAX];
+	char funcname[PATH_MAX];
+
+	/*
+	 * Child cost.
+	 * TODO: attach child cost to the real position in the funtion.
+	 * TODO: cfn=<fn> / call <ncall> addr(<fn>) / addr(call <fn>) <arccost>
+	 */
+	for (i=0 ; i<ct->pct_narc; i++) {
+		child = ct->pct_arc[i].pcta_child;
+		/* Object binary. */
+		fprintf(args.pa_graphfile, "cob=%s\n",
+		    pmcstat_string_unintern(child->pct_image->pi_fullpath));
+		/* Child function name. */
+		addr = child->pct_image->pi_vaddr + child->pct_func;
+		line = 0;
+		/* Child function source file. */
+		if (child->pct_type == PMCPL_PCT_NAME) {
+			fprintf(args.pa_graphfile, "cfi=%s\ncfn=%s\n",
+			    pmcstat_string_unintern(child->pct_ifl),
+			    pmcstat_string_unintern(child->pct_ifn));
+		} else if (pmcstat_image_addr2line(child->pct_image, addr,
+		    sourcefile, sizeof(sourcefile), &line,
+		    funcname, sizeof(funcname))) {
+			fprintf(args.pa_graphfile, "cfi=%s\ncfn=%s\n",
+				sourcefile, funcname);
+		} else {
+			if (child->pct_sym != NULL)
+				fprintf(args.pa_graphfile,
+				    "cfi=???\ncfn=%s\n",
+				    pmcstat_string_unintern(
+				        child->pct_sym->ps_name));
+			else
+				fprintf(args.pa_graphfile,
+				    "cfi=???\ncfn=%p\n", (void *)addr);
+		}
+
+		/* Child function address, line and call count. */
+		fprintf(args.pa_graphfile, "calls=%u %p %u\n",
+		    ct->pct_arc[i].pcta_call, (void *)addr, line);
+
+		/*
+		 * Call address, line, sample.
+		 * TODO: Associate call address to the right location.
+		 */
+		fprintf(args.pa_graphfile, "%p %u", (void *)paddr, pline);
+		for (j = 0; j<pmcstat_npmcs; j++)
+			fprintf(args.pa_graphfile, " %u",
+			    PMCPL_CT_SAMPLE(j, &ct->pct_arc[i].pcta_samples));
+		fprintf(args.pa_graphfile, "\n");
 	}
 }
 
@@ -775,40 +885,37 @@ pmcpl_ct_process(struct pmcstat_process *pp, struct pmcstat_pmcrecord *pmcr,
 static void
 pmcpl_ct_node_printself(struct pmcpl_ct_node *ct)
 {
-	int i, j, line;
-	uintptr_t addr;
-	struct pmcstat_symbol *sym;
+	int i, j, fline, line;
+	uintfptr_t faddr, addr;
 	char sourcefile[PATH_MAX];
 	char funcname[PATH_MAX];
 
 	/*
 	 * Object binary.
 	 */
-#ifdef PMCPL_CT_OPTIMIZEFN
-	if (pmcpl_ct_prevfn != ct->pct_image->pi_fullpath) {
-#endif
-		pmcpl_ct_prevfn = ct->pct_image->pi_fullpath;
-		fprintf(args.pa_graphfile, "ob=%s\n",
-		    pmcstat_string_unintern(pmcpl_ct_prevfn));
-#ifdef PMCPL_CT_OPTIMIZEFN
-	}
-#endif
+	fprintf(args.pa_graphfile, "ob=%s\n",
+	    pmcstat_string_unintern(ct->pct_image->pi_fullpath));
 
 	/*
 	 * Function name.
 	 */
-	if (pmcstat_image_addr2line(ct->pct_image, ct->pct_func,
-	    sourcefile, sizeof(sourcefile), &line,
+	faddr = ct->pct_image->pi_vaddr + ct->pct_func;
+	fline = 0;
+	if (ct->pct_type == PMCPL_PCT_NAME) {
+		fprintf(args.pa_graphfile, "fl=%s\nfn=%s\n",
+		    pmcstat_string_unintern(ct->pct_ifl),
+		    pmcstat_string_unintern(ct->pct_ifn));
+	} else if (pmcstat_image_addr2line(ct->pct_image, faddr,
+	    sourcefile, sizeof(sourcefile), &fline,
 	    funcname, sizeof(funcname))) {
-		fprintf(args.pa_graphfile, "fn=%s\n",
-		    funcname);
+		fprintf(args.pa_graphfile, "fl=%s\nfn=%s\n",
+		    sourcefile, funcname);
 	} else {
-		sym = pmcstat_symbol_search(ct->pct_image, ct->pct_func);
-		if (sym != NULL)
-			fprintf(args.pa_graphfile, "fn=%s\n",
-			    pmcstat_string_unintern(sym->ps_name));
+		if (ct->pct_sym != NULL)
+			fprintf(args.pa_graphfile, "fl=???\nfn=%s\n",
+			    pmcstat_string_unintern(ct->pct_sym->ps_name));
 		else
-			fprintf(args.pa_graphfile, "fn=%p\n",
+			fprintf(args.pa_graphfile, "fl=???\nfn=%p\n",
 			    (void *)(ct->pct_image->pi_vaddr + ct->pct_func));
 	}
 
@@ -816,15 +923,18 @@ pmcpl_ct_node_printself(struct pmcpl_ct_node *ct)
 	 * Self cost.
 	 */
 	if (ct->pct_ninstr > 0) {
+		/*
+		 * Per location cost.
+		 */
 		for (i = 0; i < ct->pct_ninstr; i++) {
 			addr = ct->pct_image->pi_vaddr +
 			    ct->pct_instr[i].pctf_func;
 			line = 0;
-			if (pmcstat_image_addr2line(ct->pct_image, addr,
+			pmcstat_image_addr2line(ct->pct_image, addr,
 			    sourcefile, sizeof(sourcefile), &line,
-			    funcname, sizeof(funcname)))
-				fprintf(args.pa_graphfile, "fl=%s\n", sourcefile);
-			fprintf(args.pa_graphfile, "%p %u", (void *)addr, line);
+			    funcname, sizeof(funcname));
+			fprintf(args.pa_graphfile, "%p %u",
+			    (void *)addr, line);
 			for (j = 0; j<pmcstat_npmcs; j++)
 				fprintf(args.pa_graphfile, " %u",
 				    PMCPL_CT_SAMPLE(j,
@@ -832,94 +942,155 @@ pmcpl_ct_node_printself(struct pmcpl_ct_node *ct)
 			fprintf(args.pa_graphfile, "\n");
 		}
 	} else {
-		addr = ct->pct_image->pi_vaddr + ct->pct_func;
-		line = 0;
-		if (pmcstat_image_addr2line(ct->pct_image, addr,
-		    sourcefile, sizeof(sourcefile), &line,
-		    funcname, sizeof(funcname)))
-			fprintf(args.pa_graphfile, "fl=%s\n", sourcefile);
-		fprintf(args.pa_graphfile, "* *");
+		/* Global cost function cost. */
+		fprintf(args.pa_graphfile, "%p %u", (void *)faddr, fline);
 		for (i = 0; i<pmcstat_npmcs ; i++)
 			fprintf(args.pa_graphfile, " %u",
 			    PMCPL_CT_SAMPLE(i, &ct->pct_samples));
 		fprintf(args.pa_graphfile, "\n");
 	}
+
+	pmcpl_ct_node_printchild(ct, faddr, fline);
+}
+
+static void
+pmcpl_ct_printnode(struct pmcpl_ct_node *ct)
+{
+	int i;
+
+	if (ct == pmcpl_ct_root) {
+		fprintf(args.pa_graphfile, "fn=root\n");
+		fprintf(args.pa_graphfile, "0x0 1");
+		for (i = 0; i<pmcstat_npmcs ; i++)
+			fprintf(args.pa_graphfile, " 0");
+		fprintf(args.pa_graphfile, "\n");
+		pmcpl_ct_node_printchild(ct, 0, 0);
+	} else
+		pmcpl_ct_node_printself(ct);
 }
 
 /*
- * Print node child cost.
+ * Breadth first traversal.
  */
 
 static void
-pmcpl_ct_node_printchild(struct pmcpl_ct_node *ct)
+pmcpl_ct_bfs(struct pmcpl_ct_node *ct)
 {
-	int i, j, line;
-	uintptr_t addr;
-	struct pmcstat_symbol *sym;
+	int i;
+	struct pmcpl_ct_node_hash *pch, *pchc;
 	struct pmcpl_ct_node *child;
+	STAILQ_HEAD(,pmcpl_ct_node_hash) q;
+
+	STAILQ_INIT(&q);
+	if ((pch = malloc(sizeof(*pch))) == NULL)
+		err(EX_OSERR, "ERROR: Cannot allocate queue");
+	pch->pch_ctnode = ct;
+	STAILQ_INSERT_TAIL(&q, pch, pch_next);
+	ct->pct_color = PMCPL_PCT_BLACK;
+
+	while (!STAILQ_EMPTY(&q)) {
+		pch = STAILQ_FIRST(&q);
+		STAILQ_REMOVE_HEAD(&q, pch_next);
+		pmcpl_ct_printnode(pch->pch_ctnode);
+		for (i = 0; i<pch->pch_ctnode->pct_narc; i++) {
+			child = pch->pch_ctnode->pct_arc[i].pcta_child;
+			if (child->pct_color == PMCPL_PCT_WHITE) {
+				child->pct_color = PMCPL_PCT_BLACK;
+				if ((pchc = malloc(sizeof(*pchc))) == NULL)
+					err(EX_OSERR,
+					    "ERROR: Cannot allocate queue");
+				pchc->pch_ctnode = child;
+				STAILQ_INSERT_TAIL(&q, pchc, pch_next);
+			}
+		}
+		free(pch);
+	}
+}
+
+/*
+ * Detect and fix inlined location.
+ */
+
+static void
+_pmcpl_ct_expand_inline(struct pmcpl_ct_node *ct)
+{
+	int i, j;
+	unsigned fline, line, v;
+	uintfptr_t faddr, addr, pc;
 	char sourcefile[PATH_MAX];
-	char funcname[PATH_MAX];
+	char ffuncname[PATH_MAX], funcname[PATH_MAX];
+	char buffer[PATH_MAX];
+	struct pmcpl_ct_node *child;
 
 	/*
-	 * Child cost.
-	 * TODO: attach child cost to the real position in the function.
-	 * TODO: cfn=<fn> / call <ncall> addr(<fn>) / addr(call <fn>) <arccost>
+	 * Resolve parent and compare to each instr location.
 	 */
-	for (i=0 ; i<ct->pct_narc; i++) {
-		child = ct->pct_arc[i].pcta_child;
+	faddr = ct->pct_image->pi_vaddr + ct->pct_func;
+	fline = 0;
+	if (!pmcstat_image_addr2line(ct->pct_image, faddr,
+	    sourcefile, sizeof(sourcefile), &fline,
+	    ffuncname, sizeof(ffuncname)))
+		return;
 
-		/* Object binary. */
-#ifdef PMCPL_CT_OPTIMIZEFN
-		if (pmcpl_ct_prevfn != child->pct_image->pi_fullpath) {
-#endif
-			pmcpl_ct_prevfn = child->pct_image->pi_fullpath;
-			fprintf(args.pa_graphfile, "cob=%s\n",
-			    pmcstat_string_unintern(pmcpl_ct_prevfn));
-#if PMCPL_CT_OPTIMIZEFN
-		}
-#endif
-		/* Child function name. */
-		addr = child->pct_image->pi_vaddr + child->pct_func;
-		/* Child function source file. */
-		if (pmcstat_image_addr2line(child->pct_image, addr,
+	for (i = 0; i < ct->pct_ninstr; i++) {
+		addr = ct->pct_image->pi_vaddr +
+		    ct->pct_instr[i].pctf_func;
+		line = 0;
+		if (!pmcstat_image_addr2line(ct->pct_image, addr,
 		    sourcefile, sizeof(sourcefile), &line,
-		    funcname, sizeof(funcname))) {
-			fprintf(args.pa_graphfile, "cfn=%s\n", funcname);
-			fprintf(args.pa_graphfile, "cfl=%s\n", sourcefile);
-		} else {
-			sym = pmcstat_symbol_search(child->pct_image,
-			    child->pct_func);
-			if (sym != NULL)
-				fprintf(args.pa_graphfile, "cfn=%s\n",
-				    pmcstat_string_unintern(sym->ps_name));
-			else
-				fprintf(args.pa_graphfile, "cfn=%p\n", (void *)addr);
-		}
+		    funcname, sizeof(funcname)))
+			continue;
 
-		/* Child function address, line and call count. */
-		fprintf(args.pa_graphfile, "calls=%u %p %u\n",
-		    ct->pct_arc[i].pcta_call, (void *)addr, line);
+		if (strcmp(funcname, ffuncname) == 0)
+			continue;
 
-		if (ct->pct_image != NULL) {
-			/* Call address, line, sample. */
-			addr = ct->pct_image->pi_vaddr + ct->pct_func;
-			line = 0;
-			if (pmcstat_image_addr2line(ct->pct_image, addr, sourcefile,
-			    sizeof(sourcefile), &line,
-			    funcname, sizeof(funcname)))
-				fprintf(args.pa_graphfile, "%p %u", (void *)addr, line);
-			else
-				fprintf(args.pa_graphfile, "* *");
+		/*
+		 * - Lookup/create inline node by function name.
+		 * - Move instr PMCs to the inline node.
+		 * - Link nodes.
+		 * The lookup create a specific node per image/pc.
+		 */
+		if (args.pa_verbosity >= 2)
+			fprintf(args.pa_printfile,
+			    "WARNING: inlined function at %p %s in %s\n",
+			    (void *)addr, funcname, ffuncname);
+
+		snprintf(buffer, sizeof(buffer), "%s@%s",
+			funcname, ffuncname);
+		child = pmcpl_ct_node_hash_lookup(ct->pct_image,
+		    ct->pct_func, ct->pct_sym, sourcefile, buffer);
+		assert(child != NULL);
+		pc = ct->pct_instr[i].pctf_func;
+		for (j = 0; j<pmcstat_npmcs; j++) {
+			v = PMCPL_CT_SAMPLE(j,
+			    &ct->pct_instr[i].pctf_samples);
+			if (v == 0)
+				continue;
+			pmcpl_ct_instr_add(child, j, pc, v);
+			pmcpl_ct_node_update(ct, child, j, v, 0);
+			if (j < ct->pct_samples.npmcs)
+				ct->pct_samples.sb[j] -=
+				    ct->pct_instr[i].pctf_samples.sb[j];
+			ct->pct_instr[i].pctf_samples.sb[j] = 0;
 		}
-		else
-			fprintf(args.pa_graphfile, "* *");
-		for (j = 0; j<pmcstat_npmcs; j++)
-			fprintf(args.pa_graphfile, " %u",
-			    PMCPL_CT_SAMPLE(j, &ct->pct_arc[i].pcta_samples));
-		fprintf(args.pa_graphfile, "\n");
 	}
 }
 
+static void
+pmcpl_ct_expand_inline(void)
+{
+	int i;
+	struct pmcpl_ct_node_hash *pch;
+
+	if (!args.pa_ctdumpinstr)
+		return;
+
+	for (i = 0; i < PMCSTAT_NHASH; i++)
+		STAILQ_FOREACH(pch, &pmcpl_ct_node_hash[i], pch_next)
+			if (pch->pch_ctnode->pct_type == PMCPL_PCT_ADDR)
+				_pmcpl_ct_expand_inline(pch->pch_ctnode);
+}
+
 /*
  * Clean the PMC name for Kcachegrind formula
  */
@@ -941,13 +1112,12 @@ pmcpl_ct_fixup_pmcname(char *s)
 static void
 pmcpl_ct_print(void)
 {
-	int n, i;
-	struct pmcpl_ct_node_hash *pch;
-	struct pmcpl_ct_sample rsamples;
+	int i;
 	char name[40];
+	struct pmcpl_ct_sample rsamples;
 
 	pmcpl_ct_samples_root(&rsamples);
-	pmcpl_ct_prevfn = NULL;
+	pmcpl_ct_expand_inline();
 
 	fprintf(args.pa_graphfile,
 		"version: 1\n"
@@ -964,25 +1134,8 @@ pmcpl_ct_print(void)
 	for (i=0; i<pmcstat_npmcs ; i++)
 		fprintf(args.pa_graphfile, " %u",
 		    PMCPL_CT_SAMPLE(i, &rsamples));
-	fprintf(args.pa_graphfile, "\n\n");
-
-	/*
-	 * Fake root node
-	 */
-	fprintf(args.pa_graphfile, "ob=FreeBSD\n");
-	fprintf(args.pa_graphfile, "fn=ROOT\n");
-	fprintf(args.pa_graphfile, "* *");
-	for (i = 0; i<pmcstat_npmcs ; i++)
-		fprintf(args.pa_graphfile, " 0");
 	fprintf(args.pa_graphfile, "\n");
-	pmcpl_ct_node_printchild(pmcpl_ct_root);
-
-	for (n = 0; n < PMCSTAT_NHASH; n++)
-		LIST_FOREACH(pch, &pmcpl_ct_node_hash[n], pch_next) {
-			pmcpl_ct_node_printself(pch->pch_ctnode);
-			pmcpl_ct_node_printchild(pch->pch_ctnode);
-	}
-
+	pmcpl_ct_bfs(pmcpl_ct_root);
 	pmcpl_ct_samples_free(&rsamples);
 }
 
@@ -1003,11 +1156,10 @@ pmcpl_ct_init(void)
 {
 	int i;
 
-	pmcpl_ct_prevfn = NULL;
-	pmcpl_ct_root = pmcpl_ct_node_allocate(NULL, 0);
+	pmcpl_ct_root = pmcpl_ct_node_allocate();
 
 	for (i = 0; i < PMCSTAT_NHASH; i++)
-		LIST_INIT(&pmcpl_ct_node_hash[i]);
+		STAILQ_INIT(&pmcpl_ct_node_hash[i]);
 
 	pmcpl_ct_samples_init(&pmcpl_ct_callid);
 
@@ -1030,7 +1182,7 @@ pmcpl_ct_shutdown(FILE *mf)
 	 */
 
 	for (i = 0; i < PMCSTAT_NHASH; i++) {
-		LIST_FOREACH_SAFE(pch, &pmcpl_ct_node_hash[i], pch_next,
+		STAILQ_FOREACH_SAFE(pch, &pmcpl_ct_node_hash[i], pch_next,
 		    pchtmp) {
 			pmcpl_ct_node_free(pch->pch_ctnode);
 			free(pch);
diff --git a/usr.sbin/pmcstat/pmcstat_log.c b/usr.sbin/pmcstat/pmcstat_log.c
index 41d9095..1a9ddc6 100644
--- a/usr.sbin/pmcstat/pmcstat_log.c
+++ b/usr.sbin/pmcstat/pmcstat_log.c
@@ -429,7 +429,9 @@ pmcstat_image_get_aout_params(struct pmcstat_image *image)
 
 	if ((fd = open(buffer, O_RDONLY, 0)) < 0 ||
 	    (nbytes = read(fd, &ex, sizeof(ex))) < 0) {
-		warn("WARNING: Cannot determine type of \"%s\"", path);
+		if (args.pa_verbosity >= 2)
+			warn("WARNING: Cannot determine type of \"%s\"",
+			    path);
 		image->pi_type = PMCSTAT_IMAGE_INDETERMINABLE;
 		if (fd != -1)
 			(void) close(fd);
@@ -639,8 +641,9 @@ pmcstat_image_get_elf_params(struct pmcstat_image *image)
 	if ((fd = open(buffer, O_RDONLY, 0)) < 0 ||
 	    (e = elf_begin(fd, ELF_C_READ, NULL)) == NULL ||
 	    (elf_kind(e) != ELF_K_ELF)) {
-		warnx("WARNING: Cannot determine the type of \"%s\".",
-		    buffer);
+		if (args.pa_verbosity >= 2)
+			warnx("WARNING: Cannot determine the type of \"%s\".",
+			    buffer);
 		goto done;
 	}
 
@@ -946,6 +949,7 @@ pmcstat_image_addr2line(struct pmcstat_image *image, uintfptr_t addr,
     char *funcname, size_t funcname_len)
 {
 	static int addr2line_warn = 0;
+	unsigned l;
 
 	char *sep, cmdline[PATH_MAX], imagepath[PATH_MAX];
 	int fd;
@@ -961,6 +965,11 @@ pmcstat_image_addr2line(struct pmcstat_image *image, uintfptr_t addr,
 			    pmcstat_string_unintern(image->pi_fullpath));
 		} else
 			close(fd);
+		/*
+		 * New addr2line support recursive inline function with -i
+		 * but the format does not add a marker when no more entries
+		 * are available.
+		 */
 		snprintf(cmdline, sizeof(cmdline), "addr2line -Cfe \"%s\"",
 		    imagepath);
 		image->pi_addr2line = popen(cmdline, "r+");
@@ -1002,10 +1011,10 @@ pmcstat_image_addr2line(struct pmcstat_image *image, uintfptr_t addr,
 		return (0);
 	}
 	*sep = '\0';
-	*sourceline = atoi(sep+1);
-	if (*sourceline == 0)
+	l = atoi(sep+1);
+	if (l == 0)
 		return (0);
-
+	*sourceline = l;
 	return (1);
 }