[PATCH v3 1/6] perf report: Add branch flag to callchain cursor node

[Jin Yao]

Since the branch ip has been added to call stack for easier browsing,
this patch adds more branch information. For example, add a flag to
indicate if this ip is a branch, and also add with the branch flag.

Then we can know if the cursor node represents a branch and know
what the branch flag it has.

The branch history code has a loop detection pass that removes small
loops. It would be nice for knowing how many loops were removed.
This patch records the number of removed loops in a callchain cursor
node.

Signed-off-by: Jin Yao <yao.jin@xxxxxxxxxxxxxxx>
---
 tools/perf/util/callchain.c | 13 +++++++--
 tools/perf/util/callchain.h |  7 ++++-
 tools/perf/util/machine.c   | 69 ++++++++++++++++++++++++++++++++++-----------
 3 files changed, 70 insertions(+), 19 deletions(-)

diff --git a/tools/perf/util/callchain.c b/tools/perf/util/callchain.c
index 07fd30b..7857494 100644
--- a/tools/perf/util/callchain.c
+++ b/tools/perf/util/callchain.c
@@ -730,7 +730,8 @@ merge_chain_branch(struct callchain_cursor *cursor,
 
 	list_for_each_entry_safe(list, next_list, &src->val, list) {
 		callchain_cursor_append(cursor, list->ip,
-					list->ms.map, list->ms.sym);
+					list->ms.map, list->ms.sym,
+					false, NULL, 0);
 		list_del(&list->list);
 		free(list);
 	}
@@ -767,7 +768,9 @@ int callchain_merge(struct callchain_cursor *cursor,
 }
 
 int callchain_cursor_append(struct callchain_cursor *cursor,
-			    u64 ip, struct map *map, struct symbol *sym)
+			    u64 ip, struct map *map, struct symbol *sym,
+			    bool branch, struct branch_flags *flags,
+			    int removed_loop)
 {
 	struct callchain_cursor_node *node = *cursor->last;
 
@@ -782,6 +785,12 @@ int callchain_cursor_append(struct callchain_cursor *cursor,
 	node->ip = ip;
 	node->map = map;
 	node->sym = sym;
+	node->branch = branch;
+	node->removed_loop = removed_loop;
+
+	if (flags)
+		memcpy(&node->branch_flags, flags,
+			sizeof(struct branch_flags));
 
 	cursor->nr++;
 
diff --git a/tools/perf/util/callchain.h b/tools/perf/util/callchain.h
index 13e7554..a16da59 100644
--- a/tools/perf/util/callchain.h
+++ b/tools/perf/util/callchain.h
@@ -129,6 +129,9 @@ struct callchain_cursor_node {
 	u64				ip;
 	struct map			*map;
 	struct symbol			*sym;
+	bool				branch;
+	struct branch_flags		branch_flags;
+	int				removed_loop;
 	struct callchain_cursor_node	*next;
 };
 
@@ -183,7 +186,9 @@ static inline void callchain_cursor_reset(struct callchain_cursor *cursor)
 }
 
 int callchain_cursor_append(struct callchain_cursor *cursor, u64 ip,
-			    struct map *map, struct symbol *sym);
+			    struct map *map, struct symbol *sym,
+			    bool branch, struct branch_flags *flags,
+			    int removed_loop);
 
 /* Close a cursor writing session. Initialize for the reader */
 static inline void callchain_cursor_commit(struct callchain_cursor *cursor)
diff --git a/tools/perf/util/machine.c b/tools/perf/util/machine.c
index df85b9e..7c44331 100644
--- a/tools/perf/util/machine.c
+++ b/tools/perf/util/machine.c
@@ -1616,7 +1616,10 @@ static int add_callchain_ip(struct thread *thread,
 			    struct symbol **parent,
 			    struct addr_location *root_al,
 			    u8 *cpumode,
-			    u64 ip)
+			    u64 ip,
+			    bool branch,
+			    struct branch_flags *flags,
+			    int removed_loop)
 {
 	struct addr_location al;
 
@@ -1668,7 +1671,8 @@ static int add_callchain_ip(struct thread *thread,
 
 	if (symbol_conf.hide_unresolved && al.sym == NULL)
 		return 0;
-	return callchain_cursor_append(cursor, al.addr, al.map, al.sym);
+	return callchain_cursor_append(cursor, al.addr, al.map, al.sym,
+				       branch, flags, removed_loop);
 }
 
 struct branch_info *sample__resolve_bstack(struct perf_sample *sample,
@@ -1696,12 +1700,13 @@ struct branch_info *sample__resolve_bstack(struct perf_sample *sample,
 #define PERF_MAX_BRANCH_DEPTH 127
 
 /* Remove loops. */
-static int remove_loops(struct branch_entry *l, int nr)
+static int remove_loops(struct branch_entry *l, int nr, int *removed)
 {
 	int i, j, off;
 	unsigned char chash[CHASHSZ];
 
 	memset(chash, NO_ENTRY, sizeof(chash));
+	*removed = 0;
 
 	BUG_ON(PERF_MAX_BRANCH_DEPTH > 255);
 
@@ -1724,6 +1729,7 @@ static int remove_loops(struct branch_entry *l, int nr)
 				memmove(l + i, l + i + off,
 					(nr - (i + off)) * sizeof(*l));
 				nr -= off;
+				*removed += 1;
 			}
 		}
 	}
@@ -1757,7 +1763,9 @@ static int resolve_lbr_callchain_sample(struct thread *thread,
 	/* LBR only affects the user callchain */
 	if (i != chain_nr) {
 		struct branch_stack *lbr_stack = sample->branch_stack;
-		int lbr_nr = lbr_stack->nr, j;
+		int lbr_nr = lbr_stack->nr, j, k;
+		bool branch;
+		struct branch_flags *flags;
 		/*
 		 * LBR callstack can only get user call chain.
 		 * The mix_chain_nr is kernel call chain
@@ -1772,23 +1780,41 @@ static int resolve_lbr_callchain_sample(struct thread *thread,
 
 		for (j = 0; j < mix_chain_nr; j++) {
 			int err;
+			branch = false;
+			flags = NULL;
+
 			if (callchain_param.order == ORDER_CALLEE) {
 				if (j < i + 1)
 					ip = chain->ips[j];
-				else if (j > i + 1)
-					ip = lbr_stack->entries[j - i - 2].from;
-				else
+				else if (j > i + 1) {
+					k = j - i - 2;
+					ip = lbr_stack->entries[k].from;
+					branch = true;
+					flags = &lbr_stack->entries[k].flags;
+				} else {
 					ip = lbr_stack->entries[0].to;
+					branch = true;
+					flags = &lbr_stack->entries[0].flags;
+				}
 			} else {
-				if (j < lbr_nr)
-					ip = lbr_stack->entries[lbr_nr - j - 1].from;
+				if (j < lbr_nr) {
+					k = lbr_nr - j - 1;
+					ip = lbr_stack->entries[k].from;
+					branch = true;
+					flags = &lbr_stack->entries[k].flags;
+				}
 				else if (j > lbr_nr)
 					ip = chain->ips[i + 1 - (j - lbr_nr)];
-				else
+				else {
 					ip = lbr_stack->entries[0].to;
+					branch = true;
+					flags = &lbr_stack->entries[0].flags;
+				}
 			}
 
-			err = add_callchain_ip(thread, cursor, parent, root_al, &cpumode, ip);
+			err = add_callchain_ip(thread, cursor, parent,
+					       root_al, &cpumode, ip,
+					       branch, flags, 0);
 			if (err)
 				return (err < 0) ? err : 0;
 		}
@@ -1813,6 +1839,7 @@ static int thread__resolve_callchain_sample(struct thread *thread,
 	int i, j, err, nr_entries;
 	int skip_idx = -1;
 	int first_call = 0;
+	int removed_loop, removed;
 
 	if (perf_evsel__has_branch_callstack(evsel)) {
 		err = resolve_lbr_callchain_sample(thread, cursor, sample, parent,
@@ -1868,14 +1895,21 @@ static int thread__resolve_callchain_sample(struct thread *thread,
 				be[i] = branch->entries[branch->nr - i - 1];
 		}
 
-		nr = remove_loops(be, nr);
+		nr = remove_loops(be, nr, &removed);
+		removed_loop = 0;
 
 		for (i = 0; i < nr; i++) {
+			if (i == nr - 1)
+				removed_loop = removed;
+
 			err = add_callchain_ip(thread, cursor, parent, root_al,
-					       NULL, be[i].to);
+					       NULL, be[i].to,
+					       true, &be[i].flags,
+					       removed_loop);
 			if (!err)
 				err = add_callchain_ip(thread, cursor, parent, root_al,
-						       NULL, be[i].from);
+						       NULL, be[i].from,
+						       true, &be[i].flags, 0);
 			if (err == -EINVAL)
 				break;
 			if (err)
@@ -1903,7 +1937,9 @@ static int thread__resolve_callchain_sample(struct thread *thread,
 		if (ip < PERF_CONTEXT_MAX)
                        ++nr_entries;
 
-		err = add_callchain_ip(thread, cursor, parent, root_al, &cpumode, ip);
+		err = add_callchain_ip(thread, cursor, parent,
+				       root_al, &cpumode, ip,
+				       false, NULL, 0);
 
 		if (err)
 			return (err < 0) ? err : 0;
@@ -1919,7 +1955,8 @@ static int unwind_entry(struct unwind_entry *entry, void *arg)
 	if (symbol_conf.hide_unresolved && entry->sym == NULL)
 		return 0;
 	return callchain_cursor_append(cursor, entry->ip,
-				       entry->map, entry->sym);
+				       entry->map, entry->sym,
+				       false, NULL, 0);
 }
 
 static int thread__resolve_callchain_unwind(struct thread *thread,
-- 
2.7.4