From: Namhyung Kim <namhyung@kernel.org>
To: Arnaldo Carvalho de Melo <acme@kernel.org>,
Jiri Olsa <jolsa@kernel.org>,
Peter Zijlstra <peterz@infradead.org>
Cc: Ian Rogers <irogers@google.com>,
Adrian Hunter <adrian.hunter@intel.com>,
Ingo Molnar <mingo@kernel.org>,
LKML <linux-kernel@vger.kernel.org>,
linux-perf-users@vger.kernel.org,
Linus Torvalds <torvalds@linux-foundation.org>,
Stephane Eranian <eranian@google.com>,
Masami Hiramatsu <mhiramat@kernel.org>,
linux-toolchains@vger.kernel.org,
linux-trace-devel@vger.kernel.org
Subject: [PATCH 38/48] perf annotate: Add annotate_get_basic_blocks()
Date: Wed, 11 Oct 2023 20:51:01 -0700 [thread overview]
Message-ID: <20231012035111.676789-39-namhyung@kernel.org> (raw)
In-Reply-To: <20231012035111.676789-1-namhyung@kernel.org>
The annotate_get_basic_blocks() is to find a list of basic blocks from
the source instruction to the destination instruction in a function.
It'll be used to find variables in a scope. Use BFS (Breadth First
Search) to find a shortest path to carry the variable/register state
minimally.
Also change find_disasm_line() to be used in annotate_get_basic_blocks()
and add 'allow_update' argument to control if it can update the IP.
Signed-off-by: Namhyung Kim <namhyung@kernel.org>
---
tools/perf/util/annotate.c | 219 ++++++++++++++++++++++++++++++++++++-
tools/perf/util/annotate.h | 16 +++
2 files changed, 232 insertions(+), 3 deletions(-)
diff --git a/tools/perf/util/annotate.c b/tools/perf/util/annotate.c
index 1cf55f903ee4..8384bc37831c 100644
--- a/tools/perf/util/annotate.c
+++ b/tools/perf/util/annotate.c
@@ -3642,7 +3642,8 @@ static void symbol__ensure_annotate(struct map_symbol *ms, struct evsel *evsel)
}
}
-static struct disasm_line *find_disasm_line(struct symbol *sym, u64 ip)
+static struct disasm_line *find_disasm_line(struct symbol *sym, u64 ip,
+ bool allow_update)
{
struct disasm_line *dl;
struct annotation *notes;
@@ -3655,7 +3656,8 @@ static struct disasm_line *find_disasm_line(struct symbol *sym, u64 ip)
* llvm-objdump places "lock" in a separate line and
* in that case, we want to get the next line.
*/
- if (!strcmp(dl->ins.name, "lock") && *dl->ops.raw == '\0') {
+ if (!strcmp(dl->ins.name, "lock") &&
+ *dl->ops.raw == '\0' && allow_update) {
ip++;
continue;
}
@@ -3766,7 +3768,7 @@ struct annotated_data_type *hist_entry__get_data_type(struct hist_entry *he)
* Get a disasm to extract the location from the insn.
* This is too slow...
*/
- dl = find_disasm_line(ms->sym, ip);
+ dl = find_disasm_line(ms->sym, ip, /*allow_update=*/true);
if (dl == NULL) {
ann_data_stat.no_insn++;
return NULL;
@@ -3860,3 +3862,214 @@ struct annotated_data_type *hist_entry__get_data_type(struct hist_entry *he)
istat->bad++;
return NULL;
}
+
+/* Basic block traversal (BFS) data structure */
+struct basic_block_data {
+ struct list_head queue;
+ struct list_head visited;
+};
+
+/*
+ * During the traversal, it needs to know the parent block where the current
+ * block block started from. Note that single basic block can be parent of
+ * two child basic blocks (in case of condition jump).
+ */
+struct basic_block_link {
+ struct list_head node;
+ struct basic_block_link *parent;
+ struct annotated_basic_block *bb;
+};
+
+/* Check any of basic block in the list already has the offset */
+static bool basic_block_has_offset(struct list_head *head, s64 offset)
+{
+ struct basic_block_link *link;
+
+ list_for_each_entry(link, head, node) {
+ s64 begin_offset = link->bb->begin->al.offset;
+ s64 end_offset = link->bb->end->al.offset;
+
+ if (begin_offset <= offset && offset <= end_offset)
+ return true;
+ }
+ return false;
+}
+
+static bool is_new_basic_block(struct basic_block_data *bb_data,
+ struct disasm_line *dl)
+{
+ s64 offset = dl->al.offset;
+
+ if (basic_block_has_offset(&bb_data->visited, offset))
+ return false;
+ if (basic_block_has_offset(&bb_data->queue, offset))
+ return false;
+ return true;
+}
+
+/* Add a basic block starting from dl and link it to the parent */
+static int add_basic_block(struct basic_block_data *bb_data,
+ struct basic_block_link *parent,
+ struct disasm_line *dl)
+{
+ struct annotated_basic_block *bb;
+ struct basic_block_link *link;
+
+ if (dl == NULL)
+ return -1;
+
+ if (!is_new_basic_block(bb_data, dl))
+ return 0;
+
+ bb = zalloc(sizeof(*bb));
+ if (bb == NULL)
+ return -1;
+
+ bb->begin = dl;
+ bb->end = dl;
+ INIT_LIST_HEAD(&bb->list);
+
+ link = malloc(sizeof(*link));
+ if (link == NULL) {
+ free(bb);
+ return -1;
+ }
+
+ link->bb = bb;
+ link->parent = parent;
+ list_add_tail(&link->node, &bb_data->queue);
+ return 0;
+}
+
+/* Returns true when it finds the target in the current basic block */
+static bool process_basic_block(struct basic_block_data *bb_data,
+ struct basic_block_link *link,
+ struct symbol *sym, u64 target)
+{
+ struct disasm_line *dl, *next_dl, *last_dl;
+ struct annotation *notes = symbol__annotation(sym);
+ bool found = false;
+
+ dl = link->bb->begin;
+ /* Check if it's already visited */
+ if (basic_block_has_offset(&bb_data->visited, dl->al.offset))
+ return false;
+
+ last_dl = list_last_entry(¬es->src->source,
+ struct disasm_line, al.node);
+
+ list_for_each_entry_from(dl, ¬es->src->source, al.node) {
+ /* Found the target instruction */
+ if (sym->start + dl->al.offset == target) {
+ found = true;
+ break;
+ }
+ /* End of the function, finish the block */
+ if (dl == last_dl)
+ break;
+ /* 'return' instruction finishes the block */
+ if (dl->ins.ops == &ret_ops)
+ break;
+ /* normal instructions are part of the basic block */
+ if (dl->ins.ops != &jump_ops)
+ continue;
+ /* jump to a different function, tail call or return */
+ if (dl->ops.target.outside)
+ break;
+ /* jump instruction creates new basic block(s) */
+ next_dl = find_disasm_line(sym, sym->start + dl->ops.target.offset,
+ /*allow_update=*/false);
+ add_basic_block(bb_data, link, next_dl);
+
+ /*
+ * FIXME: determine conditional jumps properly.
+ * Conditional jumps create another basic block with the
+ * next disasm line.
+ */
+ if (!strstr(dl->ins.name, "jmp")) {
+ next_dl = list_next_entry(dl, al.node);
+ add_basic_block(bb_data, link, next_dl);
+ }
+ break;
+
+ }
+ link->bb->end = dl;
+ return found;
+}
+
+/*
+ * It founds a target basic block, build a proper linked list of basic blocks
+ * by following the link recursively.
+ */
+static void link_found_basic_blocks(struct basic_block_link *link,
+ struct list_head *head)
+{
+ while (link) {
+ struct basic_block_link *parent = link->parent;
+
+ list_move(&link->bb->list, head);
+ list_del(&link->node);
+ free(link);
+
+ link = parent;
+ }
+}
+
+static void delete_basic_blocks(struct basic_block_data *bb_data)
+{
+ struct basic_block_link *link, *tmp;
+
+ list_for_each_entry_safe(link, tmp, &bb_data->queue, node) {
+ list_del(&link->node);
+ free(link->bb);
+ free(link);
+ }
+
+ list_for_each_entry_safe(link, tmp, &bb_data->visited, node) {
+ list_del(&link->node);
+ free(link->bb);
+ free(link);
+ }
+}
+
+/**
+ * annotate_get_basic_blocks - Get basic blocks for given address range
+ * @sym: symbol to annotate
+ * @src: source address
+ * @dst: destination address
+ * @head: list head to save basic blocks
+ *
+ * This function traverses disasm_lines from @src to @dst and save them in a
+ * list of annotated_basic_block to @head. It uses BFS to find the shortest
+ * path between two. The basic_block_link is to maintain parent links so
+ * that it can build a list of blocks from the start.
+ */
+int annotate_get_basic_blocks(struct symbol *sym, s64 src, s64 dst,
+ struct list_head *head)
+{
+ struct basic_block_data bb_data = {
+ .queue = LIST_HEAD_INIT(bb_data.queue),
+ .visited = LIST_HEAD_INIT(bb_data.visited),
+ };
+ struct basic_block_link *link;
+ struct disasm_line *dl;
+ int ret = -1;
+
+ dl = find_disasm_line(sym, src, /*allow_update=*/false);
+ if (add_basic_block(&bb_data, /*parent=*/NULL, dl) < 0)
+ return -1;
+
+ /* Find shortest path from src to dst using BFS */
+ while (!list_empty(&bb_data.queue)) {
+ link = list_first_entry(&bb_data.queue, struct basic_block_link, node);
+
+ if (process_basic_block(&bb_data, link, sym, dst)) {
+ link_found_basic_blocks(link, head);
+ ret = 0;
+ break;
+ }
+ list_move(&link->node, &bb_data.visited);
+ }
+ delete_basic_blocks(&bb_data);
+ return ret;
+}
diff --git a/tools/perf/util/annotate.h b/tools/perf/util/annotate.h
index 99c8d30a2fa7..c2cc9baf08be 100644
--- a/tools/perf/util/annotate.h
+++ b/tools/perf/util/annotate.h
@@ -493,4 +493,20 @@ extern struct list_head ann_insn_stat;
u64 annotate_calc_pcrel(struct map_symbol *ms, u64 ip, int offset,
struct disasm_line *dl);
+/**
+ * struct annotated_basic_block - Basic block of instructions
+ * @list: List node
+ * @begin: start instruction in the block
+ * @end: end instruction in the block
+ */
+struct annotated_basic_block {
+ struct list_head list;
+ struct disasm_line *begin;
+ struct disasm_line *end;
+};
+
+/* Get a list of basic blocks from src to dst addresses */
+int annotate_get_basic_blocks(struct symbol *sym, s64 src, s64 dst,
+ struct list_head *head);
+
#endif /* __PERF_ANNOTATE_H */
--
2.42.0.655.g421f12c284-goog
next prev parent reply other threads:[~2023-10-12 3:55 UTC|newest]
Thread overview: 96+ messages / expand[flat|nested] mbox.gz Atom feed top
2023-10-12 3:50 [RFC 00/48] perf tools: Introduce data type profiling (v1) Namhyung Kim
2023-10-12 3:50 ` [PATCH 01/48] perf annotate: Move raw_comment and raw_func_start Namhyung Kim
2023-10-12 3:50 ` [PATCH 02/48] perf annotate: Check if operand has multiple regs Namhyung Kim
2023-11-27 19:05 ` Arnaldo Carvalho de Melo
2023-10-12 3:50 ` [PATCH 03/48] perf tools: Add util/debuginfo.[ch] files Namhyung Kim
2023-10-12 3:50 ` [PATCH 04/48] perf dwarf-aux: Fix die_get_typename() for void * Namhyung Kim
2023-11-04 10:52 ` Masami Hiramatsu
2023-10-12 3:50 ` [PATCH 05/48] perf dwarf-aux: Move #ifdef code to the header file Namhyung Kim
2023-11-04 10:59 ` Masami Hiramatsu
2023-10-12 3:50 ` [PATCH 06/48] perf dwarf-aux: Add die_get_scopes() helper Namhyung Kim
2023-11-05 9:50 ` Masami Hiramatsu
2023-10-12 3:50 ` [PATCH 07/48] perf dwarf-aux: Add die_find_variable_by_reg() helper Namhyung Kim
2023-11-05 9:48 ` Masami Hiramatsu
2023-10-12 3:50 ` [PATCH 08/48] perf dwarf-aux: Factor out __die_get_typename() Namhyung Kim
2023-11-05 9:07 ` Masami Hiramatsu
2023-11-06 4:01 ` Namhyung Kim
2023-10-12 3:50 ` [PATCH 09/48] perf dwarf-regs: Add get_dwarf_regnum() Namhyung Kim
2023-11-05 8:36 ` Masami Hiramatsu
2023-11-06 4:12 ` Namhyung Kim
2023-10-12 3:50 ` [PATCH 10/48] perf annotate-data: Add find_data_type() Namhyung Kim
2023-10-12 3:50 ` [PATCH 11/48] perf annotate-data: Add dso->data_types tree Namhyung Kim
2023-10-12 3:50 ` [PATCH 12/48] perf annotate: Factor out evsel__get_arch() Namhyung Kim
2023-10-12 3:50 ` [PATCH 13/48] perf annotate: Add annotate_get_insn_location() Namhyung Kim
2023-10-23 16:38 ` Arnaldo Carvalho de Melo
2023-10-24 19:10 ` Namhyung Kim
2023-10-26 5:26 ` Namhyung Kim
2023-10-26 19:37 ` Arnaldo Carvalho de Melo
2023-10-12 3:50 ` [PATCH 14/48] perf annotate: Implement hist_entry__get_data_type() Namhyung Kim
2023-10-12 3:50 ` [PATCH 15/48] perf report: Add 'type' sort key Namhyung Kim
2023-10-23 16:53 ` Arnaldo Carvalho de Melo
2023-10-24 19:11 ` Namhyung Kim
2023-10-12 3:50 ` [PATCH 16/48] perf report: Support data type profiling Namhyung Kim
2023-10-12 3:50 ` [PATCH 17/48] perf annotate-data: Add member field in the data type Namhyung Kim
2023-10-12 3:50 ` [PATCH 18/48] perf annotate-data: Update sample histogram for type Namhyung Kim
2023-10-12 3:50 ` [PATCH 19/48] perf report: Add 'typeoff' sort key Namhyung Kim
2023-10-12 3:50 ` [PATCH 20/48] perf report: Add 'symoff' " Namhyung Kim
2023-10-12 3:50 ` [PATCH 21/48] perf annotate: Add --data-type option Namhyung Kim
2023-10-12 3:50 ` [PATCH 22/48] perf annotate: Add --type-stat option for debugging Namhyung Kim
2023-10-23 17:28 ` Arnaldo Carvalho de Melo
2023-10-23 17:40 ` Arnaldo Carvalho de Melo
2023-10-24 19:12 ` Namhyung Kim
2023-10-12 3:50 ` [PATCH 23/48] perf annotate: Add --insn-stat " Namhyung Kim
2023-10-12 3:50 ` [PATCH 24/48] perf annotate-data: Parse 'lock' prefix from llvm-objdump Namhyung Kim
2023-10-12 3:50 ` [PATCH 25/48] perf annotate-data: Handle macro fusion on x86 Namhyung Kim
2023-10-12 3:50 ` [PATCH 26/48] perf annotate-data: Handle array style accesses Namhyung Kim
2023-10-12 3:50 ` [PATCH 27/48] perf annotate-data: Add stack operation pseudo type Namhyung Kim
2023-10-12 3:50 ` [PATCH 28/48] perf dwarf-aux: Add die_find_variable_by_addr() Namhyung Kim
2023-11-06 15:25 ` Masami Hiramatsu
2023-11-09 5:36 ` Namhyung Kim
2023-10-12 3:50 ` [PATCH 29/48] perf annotate-data: Handle PC-relative addressing Namhyung Kim
2023-10-12 3:50 ` [PATCH 30/48] perf annotate-data: Support global variables Namhyung Kim
2023-10-12 3:50 ` [PATCH 31/48] perf dwarf-aux: Add die_get_cfa() Namhyung Kim
2023-11-07 0:50 ` Masami Hiramatsu
2023-11-08 5:28 ` Namhyung Kim
2023-10-12 3:50 ` [PATCH 32/48] perf annotate-data: Support stack variables Namhyung Kim
2023-10-12 3:50 ` [PATCH 33/48] perf dwarf-aux: Check allowed DWARF Ops Namhyung Kim
2023-11-07 9:32 ` Masami Hiramatsu
2023-11-08 5:34 ` Namhyung Kim
2023-10-12 3:50 ` [PATCH 34/48] perf dwarf-aux: Add die_collect_vars() Namhyung Kim
2023-11-08 10:52 ` Masami Hiramatsu
2023-11-09 5:05 ` Namhyung Kim
2023-10-12 3:50 ` [PATCH 35/48] perf dwarf-aux: Handle type transfer for memory access Namhyung Kim
2023-11-08 10:57 ` Masami Hiramatsu
2023-10-12 3:50 ` [PATCH 36/48] perf annotate-data: Introduce struct data_loc_info Namhyung Kim
2023-12-03 16:22 ` Athira Rajeev
2023-12-05 0:10 ` Namhyung Kim
2023-12-05 7:17 ` Athira Rajeev
2023-10-12 3:51 ` [PATCH 37/48] perf map: Add map__objdump_2rip() Namhyung Kim
2023-10-12 3:51 ` Namhyung Kim [this message]
2023-10-12 3:51 ` [PATCH 39/48] perf annotate-data: Maintain variable type info Namhyung Kim
2023-10-12 3:51 ` [PATCH 40/48] perf annotate-data: Add update_insn_state() Namhyung Kim
2023-10-12 3:51 ` [PATCH 41/48] perf annotate-data: Handle global variable access Namhyung Kim
2023-10-12 3:51 ` [PATCH 42/48] perf annotate-data: Handle call instructions Namhyung Kim
2023-10-12 3:51 ` [PATCH 43/48] perf annotate-data: Implement instruction tracking Namhyung Kim
2023-10-12 3:51 ` [PATCH 44/48] perf annotate: Parse x86 segment register location Namhyung Kim
2023-10-12 3:51 ` [PATCH 45/48] perf annotate-data: Handle this-cpu variables in kernel Namhyung Kim
2023-10-12 3:51 ` [PATCH 46/48] perf annotate-data: Track instructions with a this-cpu variable Namhyung Kim
2023-10-12 3:51 ` [PATCH 47/48] perf annotate-data: Add stack canary type Namhyung Kim
2023-10-12 3:51 ` [PATCH 48/48] perf annotate-data: Add debug message Namhyung Kim
2023-10-12 6:03 ` [RFC 00/48] perf tools: Introduce data type profiling (v1) Ingo Molnar
2023-10-12 16:19 ` Namhyung Kim
2023-10-12 18:33 ` Ingo Molnar
2023-10-12 20:45 ` Namhyung Kim
2023-10-12 9:11 ` Peter Zijlstra
2023-10-12 16:41 ` Namhyung Kim
[not found] ` <CADzB+2mu98v9EUsA1Y-wVDSrXT2kznKi87Tb6QdN5y4mMFNsyg@mail.gmail.com>
2023-10-25 5:58 ` Namhyung Kim
2023-10-12 9:15 ` Peter Zijlstra
2023-10-12 16:52 ` Namhyung Kim
2023-10-13 14:15 ` Arnaldo Carvalho de Melo
2023-10-23 21:58 ` Andi Kleen
2023-10-24 19:16 ` Namhyung Kim
2023-10-25 2:09 ` Andi Kleen
2023-10-25 5:51 ` Namhyung Kim
2023-10-25 20:01 ` Andi Kleen
2023-11-08 17:12 ` Joe Mario
2023-11-09 4:48 ` Namhyung Kim
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20231012035111.676789-39-namhyung@kernel.org \
--to=namhyung@kernel.org \
--cc=acme@kernel.org \
--cc=adrian.hunter@intel.com \
--cc=eranian@google.com \
--cc=irogers@google.com \
--cc=jolsa@kernel.org \
--cc=linux-kernel@vger.kernel.org \
--cc=linux-perf-users@vger.kernel.org \
--cc=linux-toolchains@vger.kernel.org \
--cc=linux-trace-devel@vger.kernel.org \
--cc=mhiramat@kernel.org \
--cc=mingo@kernel.org \
--cc=peterz@infradead.org \
--cc=torvalds@linux-foundation.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).