1# Copyright (c) 2024, Alexander Lerach
  2# Copyright (c) 2024, Auterion AG
  3# SPDX-License-Identifier: BSD-3-Clause
  4
  5"""
  6# Analyze inline function usage
  7
  8Function inlining generally is a space-time tradeoff where more inlining helps
  9with execution speed but increases FLASH usage. This tool helps to see which
 10functions are inlined where and how much FLASH usage this inlining causes.
 11
 12## Command Line Interface
 13
 14You can analyze the inline usage like this:
 15
 16```sh
 17python3 -m emdbg.analyze.inline -f test.elf
 18```
 19
 20The analysis can take some time as it has to traverse all DIEs of the DWARF data.
 21"""
 22
 23from __future__ import annotations
 24from collections import defaultdict
 25from dataclasses import dataclass
 26from pathlib import Path
 27import argparse
 28import logging
 29import posixpath
 30
 31from elftools.elf.elffile import ELFFile
 32from elftools.dwarf.die import DIE
 33from elftools.dwarf.lineprogram import LineProgram
 34from elftools.dwarf.ranges import RangeEntry, RangeLists
 35
 36import rich
 37from rich.console import Console
 38from rich.table import Table
 39
 40_LOGGER = logging.getLogger(__name__)
 41
 42
 43def _rel_file_name(file_name: Path) -> str:
 44    """Return the filename relative to the CWD"""
 45    try: return str(Path(file_name).relative_to(Path().cwd()))
 46    except ValueError: return str(Path(file_name))
 47
 48# -----------------------------------------------------------------------------
 49@dataclass
 50class InlinedInstance:
 51    """
 52    See `InlinedFunction`.
 53    """
 54    translation_unit: str
 55    """name of the translation unit this instance is used in."""
 56    file_name: Path
 57    """file where the function is inlined to."""
 58    file_line: int
 59    """line within the file where the function is inlined."""
 60    size: int
 61    """amount of flash used by the inlined function in this instance."""
 62
 63
 64# -----------------------------------------------------------------------------
 65@dataclass
 66class InlinedFunction:
 67    """
 68    The `InlinedFunction` represents a function that is inlined into different callers.
 69    It contains a list of `InlinedInstance` which represent the instance that this function is inlined into.
 70    """
 71    file_name: Path
 72    """file where the inline function is declared."""
 73    file_line: int
 74    """line within the file where the inline function is declared."""
 75    total_size: int
 76    """total amount of flash used due to this method being inline."""
 77    total_size_wo_overhead: int
 78    """total amount of flash used due to this method being inline, reduced by the function call instruction overheads."""
 79    inlined_instances: list[InlinedInstance]
 80    """list of instances where this function is inlined to."""
 81
 82    def print(self, console: Console, num_of_instances: int, total_size: int, total_size_wo_overhead: int, call_overhead: int) -> str:
 83        """
 84        Prints the inlined function and its instances to the console in an easy-to-read format.
 85
 86        :param console: console to print the output to.
 87        :param num_of_instances: the number of inlined instances to print. A value of `0` causes all to be displayed.
 88        :param total_size: total amount of FLASH used by inlined functions. Used to calculate the percentage caused by this inlined function.
 89        :param total_size_wo_overhead: total amount of FLASH used by inlined functions, reduced by the function call instruction overheads.
 90        :param call_overhead: expected instruction overhead caused by a function call.
 91        """
 92        console.print((
 93            f"{_rel_file_name(self.file_name)}:{self.file_line}"
 94            f" -- Total Size: {self.total_size}"
 95            f" ({(100 if total_size == 0 else (self.total_size / total_size * 100)):.2f}%)"
 96            f" -- Total Size without instruction overhead: {self.total_size_wo_overhead}"
 97            f" ({(100 if total_size_wo_overhead == 0 else (self.total_size_wo_overhead / total_size_wo_overhead * 100)):.2f}%)"
 98        ))
 99
100        table = Table(box=rich.box.MINIMAL_DOUBLE_HEAD)
101        table.add_column("Translation unit")
102        table.add_column("File name")
103        table.add_column("File line")
104        table.add_column("Size")
105        table.add_column("Call instruction overhead")
106        table.add_column("%")
107
108        for i, inlined_instance in enumerate(self.inlined_instances):
109            if i < num_of_instances or num_of_instances == 0:
110                table.add_row(_rel_file_name(inlined_instance.translation_unit), _rel_file_name(inlined_instance.file_name), str(inlined_instance.file_line),
111                              str(inlined_instance.size), str(call_overhead),
112                              "{:.2f}".format(100 if self.total_size == 0 else inlined_instance.size / self.total_size * 100))
113            else:
114                table.add_row("...", "...", "...")
115                break
116
117        console.print(table)
118
119
120# -----------------------------------------------------------------------------
121@dataclass
122class AnalysisResult:
123    """
124    The class `AnalysisResult` represents the result of an inline analysis performed using `InlineAnalyzer`
125    """
126    inlined_savings_list: list[InlinedFunction]
127    """inlined functions with more than one instance. These allow for potential FLASH savings."""
128    inlined_no_savings_list: list[InlinedFunction]
129    """inlined functions with one instance."""
130    savings_total_size: int
131    """overall FLASH size used by inlined functions with more than one instance."""
132    no_savings_total_size: int
133    """overall FLASH size used by inlined functions with one instance."""
134    savings_total_size_wo_overhead: int
135    """overall FLASH size used by inlined functions with more than one instance, reduced by function call instruction overheads."""
136    no_savings_total_size_wo_overhead: int
137    """overall FLASH size used by inlined functions with one instance, reduced by function call instruction overheads."""
138
139
140# -----------------------------------------------------------------------------
141class InlineAnalyzer:
142    """
143    Analyzes an ELF file and DWARF debugging data to identify inline functions and the instances where they are inlined to.
144    This allows to identify options for a space-time tradeoff.
145
146    :param call_overhead: expected instruction overhead caused by a function call.
147    """
148    def __init__(self, call_overhead: int):
149        self._call_overhead = call_overhead
150        self._raw_inlined_functions = defaultdict(list)
151
152
153    def get_inlined_functions(self, file_name: str) -> AnalysisResult:
154        """
155        Returns the identified `InlinedFunction` in the given ELF file.
156        This is only possible if DWARF debugging data is available which contains debug ranges and line program.
157
158        :param file_name: path to the ELF file to analyze.
159
160        :return: on success, a `AnalysisResult` is returned. In case of errors an exception is raised.
161
162        :raises ValueError: if the debugging data is not sufficient of the analysis.
163        """
164        _LOGGER.info(f"Processing file: {file_name}")
165        self._raw_inlined_functions.clear()
166
167        with open(file_name, "rb") as f:
168            elf_file = ELFFile(f)
169
170            if not elf_file.has_dwarf_info():
171                raise ValueError(f"{file_name} has no DWARF info.")
172
173            dwarf_info = elf_file.get_dwarf_info()
174            range_lists = dwarf_info.range_lists()
175
176            for CU in dwarf_info.iter_CUs():
177                line_program = dwarf_info.line_program_for_CU(CU)
178
179                if line_program is None:
180                    _LOGGER.warning("CU @ {CU.cu_offset} DWARF info is missing line program. Skipping CU.")
181                    continue
182
183                top_die = CU.get_top_DIE()
184                self.die_get_inlined_rec(top_die, line_program, range_lists)
185        return self.raw_inlined_to_output()
186
187
188    def die_get_inlined_rec(self, die: DIE, line_program: LineProgram, range_lists: RangeLists):
189        """
190        Recursively traverse all DIEs of a given top DIE and extract information about inlined functions.
191
192        :param die: DIE to be processed. Is gathered recursively after passing a top DIE.
193        :param line_program: `LineProgram` extracted from the DWARF debugging data.
194        :param range_lists: `RangeLists` extracted from the DWARF debugging data.
195        """
196        if die.tag == "DW_TAG_inlined_subroutine" and {"DW_AT_call_file"} <= die.attributes.keys():
197            call_file = self.get_file_name(die.attributes["DW_AT_call_file"].value, line_program)
198            call_line = die.attributes["DW_AT_call_line"].value
199            size = self.get_size(die, range_lists)
200
201            decl_die = self.resolve_die_ref(die, die.cu.cu_offset + die.attributes["DW_AT_abstract_origin"].value)
202
203            if {"DW_AT_decl_file", "DW_AT_decl_line"} <= decl_die.attributes.keys():
204                decl_file = self.get_file_name(decl_die.attributes["DW_AT_decl_file"].value, line_program)
205                decl_line = decl_die.attributes["DW_AT_decl_line"].value
206                translation_unit_name = self.get_translation_unit_name(die)
207
208                called_function = InlinedInstance(translation_unit_name, call_file, call_line, size)
209                self._raw_inlined_functions[(decl_file, decl_line)].append(called_function)
210
211        # Recurse into the DIE children
212        for child in die.iter_children():
213                self.die_get_inlined_rec(child, line_program, range_lists)
214
215
216    def get_file_name(self, file_idx: int, line_program: LineProgram) -> Path:
217        """
218        Returns a file name given a DIE file index. To perform this mapping the line program is required.
219
220        :param file_idx: DIE file index for which the file name shall be returned.
221        :param line_program: `LineProgram` extracted from the DWARF debugging data.
222
223        :return: the file name for the given DIE file index. This will include the full path if the line program
224                 contains the relevant data. Otherwise, only the file name without path will be returned.
225        """
226        lp_header = line_program.header
227        file_entries = lp_header["file_entry"]
228        file_entry = file_entries[file_idx - 1]
229        dir_index = file_entry["dir_index"]
230
231        if dir_index == 0:
232            return Path(file_entry.name.decode())
233
234        directory = lp_header["include_directory"][dir_index - 1]
235        return Path(directory.decode()) / file_entry.name.decode()
236
237    def get_translation_unit_name(self, die: DIE) -> str:
238        """
239        Returns the name of the translation unit the given DIE is contained in. If the name can't be retrieved,
240        an empty string will be returned.
241
242        :param die: DIE for which the translation unit name shall be returned.
243
244        :return: on success, name of the translation unit. Otherwise, an empty string will be returned.
245        """
246        cu = self.resolve_die_ref(die, die.cu.cu_die_offset)
247
248        if {"DW_AT_name"} <= cu.attributes.keys():
249            return cu.attributes["DW_AT_name"].value.decode()
250        else:
251            return ""
252
253    def get_size(self, die: DIE, range_lists: RangeLists) -> int:
254        """
255        Returns the size required by the given DIE. The function will try different methods to get the size depending on the
256        attributes being present in the DIE. If none of the methods are successful, `0` will be returned.
257
258        :param die: DIE for which the size shall be returned.
259        :param range_lists: `RangeLists` extracted from the DWARF debugging data.
260
261        :return: on success, the size of the DIE. Otherwise, `0` will be returned.
262        """
263        if {"DW_AT_high_pc"} <= die.attributes.keys():
264            return die.attributes["DW_AT_high_pc"].value
265        if {"DW_AT_ranges"} <= die.attributes.keys():
266            if range_lists is None:
267                raise ValueError(f"DWARF info is missing debug ranges, which is required for DIE: {die}.")
268
269            range_list = range_lists.get_range_list_at_offset(die.attributes["DW_AT_ranges"].value)
270            size = 0
271            for entry in range_list:
272                if isinstance(entry, RangeEntry):
273                    size = size + (entry.end_offset - entry.begin_offset)
274            return size
275        return 0
276
277
278    def resolve_die_ref(self, die: DIE, ref_addr: int) -> DIE:
279        """
280        Given a DIE containing a reference address, the DIE referenced by that address will be returned.
281
282        :param die: DIE containing a reference address to be resolved.
283        :param ref_addr: reference address pointing to another DIE.
284
285        :return: referenced DIE.
286        """
287        return die.cu.get_DIE_from_refaddr(ref_addr)
288
289
290    def raw_inlined_to_output(self) -> AnalysisResult:
291        """
292        Performs post-processing on the gathered data about inlined functions to bring it into an easy-to-use format.
293        This includes wrapping the data into classes, grouping into inlined functions with and without FLASH saving potential
294        and sorting by the amount of FLASH used.
295
296        :return: a `AnalysisResult`.
297        """
298        inlined_savings_list = []
299        inlined_no_savings_list = []
300
301        savings_total_size = 0
302        no_savings_total_size = 0
303        savings_total_size_wo_overhead = 0
304        no_savings_total_size_wo_overhead = 0
305
306        for (decl_file, decl_line) in self._raw_inlined_functions:
307            inlined_instances = []
308            total_size = 0
309
310            for inlined_instance in self._raw_inlined_functions[(decl_file, decl_line)]:
311                inlined_instances.append(inlined_instance)
312                total_size = total_size + inlined_instance.size
313            total_size_wo_overhead = max(total_size - (len(inlined_instances) * self._call_overhead), 0)
314            inlined_function = InlinedFunction(decl_file, decl_line, total_size, total_size_wo_overhead, inlined_instances)
315
316            if len(inlined_instances) > 1:
317                inlined_savings_list.append(inlined_function)
318                savings_total_size = savings_total_size + total_size
319                savings_total_size_wo_overhead = savings_total_size_wo_overhead + total_size_wo_overhead
320            else:
321                inlined_no_savings_list.append(inlined_function)
322                no_savings_total_size = no_savings_total_size + total_size
323                no_savings_total_size_wo_overhead = no_savings_total_size_wo_overhead + total_size_wo_overhead
324
325        inlined_savings_list.sort(key=lambda x: x.total_size_wo_overhead, reverse=True)
326        inlined_no_savings_list.sort(key=lambda x: x.total_size_wo_overhead, reverse=True)
327        return AnalysisResult(inlined_savings_list, inlined_no_savings_list, savings_total_size, no_savings_total_size,
328                              savings_total_size_wo_overhead, no_savings_total_size_wo_overhead)
329
330
331# -----------------------------------------------------------------------------
332if __name__ == "__main__":
333    parser = argparse.ArgumentParser(description="Inline function analyzer to identify potential FLASH savings.")
334    parser.add_argument(
335        "-f",
336        dest="file",
337        help="Path to the ELF file to analyze",
338        required=True
339    )
340    parser.add_argument(
341        "-n",
342        help="Number of inlined functions to display. The default value of 0 causes all inlined functions to be displayed.",
343        type=int,
344        default=0
345    )
346    parser.add_argument(
347        "-m",
348        help="Number of inline function instances to show for each inlined function. The default value of 0 causes all instances to be displayed.",
349        type=int,
350        default=0
351    )
352    parser.add_argument(
353        "--overhead",
354        help="Expected instruction overhead caused by a function call, and therefore needs to be removed from the saveable space. This should include at least one branch instruction.",
355        type=int,
356        default=8
357    )
358    parser.add_argument(
359        "--all",
360        action="store_true",
361        default=False,
362        help="Include inlined functions that don't offer FLASH saving potential, i.e. functions that are only inlined once."
363    )
364
365    args = parser.parse_args()
366
367    console = Console()
368    inline_analyzer = InlineAnalyzer(args.overhead)
369    analysis_result = inline_analyzer.get_inlined_functions(args.file)
370
371    for i, inlined_function in enumerate(analysis_result.inlined_savings_list):
372        if i < args.n or args.n == 0:
373            inlined_function.print(console, args.m, analysis_result.savings_total_size, analysis_result.savings_total_size_wo_overhead, args.overhead)
374            console.print("")
375        else:
376            console.print("[...]")
377            break
378
379    if args.all:
380        for i, inlined_function in enumerate(analysis_result.inlined_no_savings_list):
381            if i < args.n or args.n == 0:
382                inlined_function.print(console, args.m, analysis_result.no_savings_total_size, analysis_result.no_savings_total_size_wo_overhead, args.overhead)
383                console.print("")
384            else:
385                console.print("[...]")
386                break
387
388    console.print(f"Total potentially saveable space: {analysis_result.savings_total_size}")
389    console.print(f"Total potentially saveable space without instruction overhead: {analysis_result.savings_total_size_wo_overhead}")
390
391    if args.all:
392        console.print(f"Total non-saveable space: {analysis_result.no_savings_total_size}")
393        console.print(f"Total non-saveable space without instruction overhead: {analysis_result.no_savings_total_size_wo_overhead}")