Gráfico de llamadas

Un grafo de llamadas (también conocido como multigrafo de llamadas ^{[ 1 ] [ 2 ]} ) es un grafo de flujo de control [ ^{3 ] que representa las} relaciones de llamada entre subrutinas en un programa informático . Cada nodo representa un procedimiento y cada arista (f, g) indica que el procedimiento f llama al procedimiento g . Por lo tanto, un ciclo en el grafo indica llamadas recursivas a procedimientos.

Los grafos de llamadas pueden ser dinámicos o estáticos. ^{[ 4 ]} Un grafo de llamadas dinámico es un registro de la ejecución del programa, por ejemplo, como resultado de un analizador de rendimiento. Por lo tanto, un grafo de llamadas dinámico puede ser exacto, pero solo describe una ejecución del programa. Un grafo de llamadas estático es un grafo de llamadas diseñado para representar todas las posibles ejecuciones del programa. El grafo de llamadas estático exacto es un problema indecidible , por lo que los algoritmos de grafos de llamadas estáticos generalmente son sobreaproximaciones. Es decir, cada relación de llamada que ocurre está representada en el grafo, y posiblemente también algunas relaciones de llamada que nunca ocurrirían en ejecuciones reales del programa.

Los grafos de llamadas se pueden definir para representar distintos grados de precisión. Un grafo de llamadas más preciso se aproxima con mayor exactitud al comportamiento del programa real, a costa de un mayor tiempo de cálculo y un mayor consumo de memoria. El grafo de llamadas más preciso es totalmente sensible al contexto , lo que significa que, para cada procedimiento, el grafo contiene un nodo independiente para cada pila de llamadas con la que se puede activar dicho procedimiento. Un grafo de llamadas totalmente sensible al contexto se denomina árbol de contexto de llamadas . Este se puede calcular fácilmente de forma dinámica, aunque puede consumir una gran cantidad de memoria. Los árboles de contexto de llamadas no suelen calcularse de forma estática, ya que tardarían demasiado en un programa grande. El grafo de llamadas menos preciso es insensible al contexto , lo que significa que solo hay un nodo para cada procedimiento.

Con lenguajes que incluyen despacho dinámico (por ejemplo, Java o C++ ), ^{[ 5 ]} funciones de primera clase (por ejemplo, Python o Racket ) o punteros a funciones (por ejemplo, C ), el cálculo preciso de un grafo de llamadas estático requiere los resultados del análisis de alias . A la inversa, el cálculo preciso de alias requiere un grafo de llamadas. Muchos sistemas de análisis estático resuelven la aparente regresión infinita calculando ambos simultáneamente.

Los grafos de llamadas pueden utilizarse de diversas maneras. Una aplicación sencilla consiste en encontrar procedimientos que nunca se llaman. Los grafos de llamadas pueden servir como documentación para que los humanos comprendan los programas . ^{[ 6 ]} También pueden utilizarse para detectar anomalías en la ejecución de programas o ataques de inyección de código. ^{[ 7 ]}

Un ejemplo de gráfico de llamadas generado a partir del autoanálisis de gprof :

índice llamado nombre |índice llamado nombre 72384/72384 sym_id_parse [54] | 1508/1508 cg_dfn [15] [3] 72384 coincidencias [3] |[13] 1508 visitas previas [13] ---------------------- |---------------------- 4/9052 cg_tally [32] | 1508/1508 cg_assemble [38] 3016/9052 hist_print [49] |[14] 1508 propagate_time [14] 6032/9052 propagate_flags [52] |---------------------- [4] 9052 sym_lookup [4] | 2 cg_dfn [15] ---------------------- | 1507/1507 cg_assemble [38] 5766/5766 core_create_function_syms [41]|[15] 1507+2 cg_dfn [15] [5] 5766 core_sym_class [5] | 1509/1509 está numerado [9] ---------------------- | 1508/1508 está_ocupado [11] 24/1537 parse_spec [19] | 1508/1508 pre_visit [13] 1513/1537 core_create_function_syms [41]| 1508/1508 post_visit [12] [6] 1537 sym_init [6] | 2 cg_dfn [15] ---------------------- |---------------------- 1511/1511 core_create_function_syms [41]| 1505/1505 hist_print [49] [7] 1511 get_src_info [7] |[16] 1505 print_line [16] ---------------------- | 2/9 print_name_only [25] 2/1510 arc_add [31] |---------------------- 1508/1510 cg_assemble [38] | 1430/1430 core_create_function_syms [41] [8] 1510 arc_lookup [8] |[17] 1430 source_file_lookup_path [17] ---------------------- |---------------------- 1509/1509 cg_dfn [15] | 24/24 sym_id_parse [54] [9] 1509 está_numerado [9] |[18] 24 parse_id [18] ---------------------- | 24/24 parse_spec [19] 1508/1508 propagate_flags [52] |---------------------- [10] 1508 inherit_flags [10] | 24/24 parse_id [18] ---------------------- |[19] 24 parse_spec [19] 1508/1508 cg_dfn [15] | 24/1537 sym_init [6] [11] 1508 está_ocupado [11] |---------------------- ---------------------- | 24/24 principal [1210] 1508/1508 cg_dfn [15] |[20] 24 sym_id_add [20] [12] 1508 post_visit [12] | 

• Visualización de software
• Grafo de dependencias