From 9895df71ae6ea14e09478cc243227b7b3a2139a3 Mon Sep 17 00:00:00 2001
From: Cyrille Bagard <nocbos@gmail.com>
Date: Sat, 26 Mar 2016 20:56:04 +0100
Subject: Extracted the logic of code nodes for better processing.
---
ChangeLog | 16 ++
src/analysis/disass/Makefile.am | 1 +
src/analysis/disass/dragon.c | 541 ++++++++++++++++++++++++++++++++++++++++
src/analysis/disass/dragon.h | 81 ++++++
src/analysis/disass/loop.c | 366 +++------------------------
src/common/bits.c | 2 +-
src/common/bits.h | 2 +-
7 files changed, 675 insertions(+), 334 deletions(-)
create mode 100644 src/analysis/disass/dragon.c
create mode 100644 src/analysis/disass/dragon.h
diff --git a/ChangeLog b/ChangeLog
index 234f547..dc07b31 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,19 @@
+16-03-26 Cyrille Bagard <nocbos@gmail.com>
+
+ * src/analysis/disass/Makefile.am:
+ Add the 'dragon.[ch]' files to libanalysisdisass_la_SOURCES.
+
+ * src/analysis/disass/dragon.c:
+ * src/analysis/disass/dragon.h:
+ New entries: extract the logic of code nodes for better processing.
+
+ * src/analysis/disass/loop.c:
+ Update code.
+
+ * src/common/bits.c:
+ * src/common/bits.h:
+ Mark bit fields as constant when needed.
+
16-03-24 Cyrille Bagard <nocbos@gmail.com>
* src/gui/editem.c:
diff --git a/src/analysis/disass/Makefile.am b/src/analysis/disass/Makefile.am
index 54b0fa5..3231749 100644
--- a/src/analysis/disass/Makefile.am
+++ b/src/analysis/disass/Makefile.am
@@ -4,6 +4,7 @@ noinst_LTLIBRARIES = libanalysisdisass.la
libanalysisdisass_la_SOURCES = \
area.h area.c \
disassembler.h disassembler.c \
+ dragon.h dragon.c \
fetch.h fetch.c \
limit.h limit.c \
links.h links.c \
diff --git a/src/analysis/disass/dragon.c b/src/analysis/disass/dragon.c
new file mode 100644
index 0000000..2fcf830
--- /dev/null
+++ b/src/analysis/disass/dragon.c
@@ -0,0 +1,541 @@
+
+/* Chrysalide - Outil d'analyse de fichiers binaires
+ * dragon.c - capacités apportées par la lecture du livre du dragon
+ *
+ * Copyright (C) 2016 Cyrille Bagard
+ *
+ * This file is part of Chrysalide.
+ *
+ * OpenIDA is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * OpenIDA is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with Foobar. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+
+#include "dragon.h"
+
+
+#include <assert.h>
+#include <malloc.h>
+
+
+
+/* ---------------------------- ENCAPSULATION DES NOEUDS ---------------------------- */
+
+
+/* Description de noeud, en référence à "Compilers: Principles, Techniques, and Tools" */
+struct _dragon_node
+{
+ GArchInstruction *first; /* Arrivée d'un lien (début) */
+ GArchInstruction *last; /* Départ d'un lien (fin) */
+
+ bitfield_t *bits; /* Représentation par masque */
+
+};
+
+
+/* Définition des blocs d'allocation */
+#define NODE_ALLOC_SIZE 100
+
+
+/* Dénombre le nombre de noeuds présents dans une routine. */
+static dragon_node *create_dragon_nodes(const GArchProcessor *, const instr_coverage *, const mrange_t *, const vmpa2t *, size_t *);
+
+/* Supprime de la mémoire tous les noeuds détectés. */
+static void delete_dragon_nodes(dragon_node *, size_t);
+
+/* Termine l'initialisation de noeuds trouvés dans une routine. */
+static void init_mask_for_nodes(dragon_node *, size_t);
+
+
+
+/* ---------------------------- ENCAPSULATION DES NOEUDS ---------------------------- */
+
+
+/* Concentration de tous les efforts */
+struct _dragon_knight
+{
+ dragon_node *nodes; /* Noeuds mis en place */
+ size_t count; /* Taille de la liste */
+
+};
+
+
+
+/* ---------------------------------------------------------------------------------- */
+/* DECOUPAGES DE CODE EN NOEUDS */
+/* ---------------------------------------------------------------------------------- */
+
+
+/******************************************************************************
+* *
+* Paramètres : proc = ensemble d'instructions à parcourir. *
+* coverage = zone de couverture où rechercher des instructions.*
+* range = zone de couverture de la routine analysée. *
+* start = adresse du début de l'analyse. *
+* count = taille de la liste de noeuds retournés. [OUT] *
+* *
+* Description : Dénombre le nombre de noeuds présents dans une routine. *
+* *
+* Retour : Liste de noeuds initialisés de façon incomplète. *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+static dragon_node *create_dragon_nodes(const GArchProcessor *proc, const instr_coverage *coverage, const mrange_t *range, const vmpa2t *start, size_t *count)
+{
+ dragon_node *result; /* Liste à créer et renvoyer */
+ size_t allocated; /* Dimensionnement en mémoire */
+ GArchInstruction *last; /* Mémorisation du passé */
+ GArchInstruction *iter; /* Boucle de parcours */
+ const mrange_t *irange; /* Emplacement d'instruction */
+ InstructionLinkType *types; /* Type de lien entre instr. */
+ size_t scount; /* Nombre de liens de dest. */
+ size_t i; /* Boucle de parcours */
+ dragon_node *new; /* Nouvel élément à créer */
+
+ result = NULL;
+ *count = 0;
+
+ allocated = 0;
+
+ for (last = NULL, iter = g_arch_processor_find_covered_instr_by_address(proc, coverage, start);
+ iter != NULL;
+ last = iter, iter = g_arch_instruction_get_next_iter(iter /* FIXME : list*/, iter, ~0))
+ {
+ /* L'instruction sort-elle des clous ? */
+
+ irange = g_arch_instruction_get_range(iter);
+
+ if (!mrange_contains_mrange(range, irange))
+ break;
+
+ /* Analyse des sources */
+
+ if (result == NULL)
+ {
+ (*count)++;
+
+ if (*count >= allocated)
+ {
+ allocated += NODE_ALLOC_SIZE;
+ result = (dragon_node *)realloc(result, allocated * sizeof(dragon_node));
+ }
+
+ new = &result[*count - 1];
+
+ new->first = iter;
+
+ }
+ else
+ {
+ scount = g_arch_instruction_get_sources(iter, NULL, &types);
+ if (scount == 0) continue;
+
+ for (i = 0; i < scount; i++)
+ switch (types[i])
+ {
+ case ILT_EXEC_FLOW:
+ case ILT_JUMP:
+ case ILT_CASE_JUMP:
+ case ILT_JUMP_IF_TRUE:
+ case ILT_JUMP_IF_FALSE:
+
+ if (*count > 0)
+ result[*count - 1].last = last;
+
+ (*count)++;
+ i = scount;
+
+ if (*count >= allocated)
+ {
+ allocated += NODE_ALLOC_SIZE;
+ result = (dragon_node *)realloc(result, allocated * sizeof(dragon_node));
+ }
+
+ new = &result[*count - 1];
+
+ new->first = iter;
+
+ break;
+
+ default:
+ break;
+
+ }
+
+ }
+
+ }
+
+ if (*count > 0)
+ result[*count - 1].last = last;
+
+ return result;
+
+}
+
+
+/******************************************************************************
+* *
+* Paramètres : nodes = liste de noeuds détectés dans une routine. *
+* count = taille de cette liste de noeuds à traiter. *
+* *
+* Description : Supprime de la mémoire tous les noeuds détectés. *
+* *
+* Retour : - *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+static void delete_dragon_nodes(dragon_node *nodes, size_t count)
+{
+ size_t i; /* Boucle de parcours */
+
+ for (i = 0; i < count; i++)
+ delete_bit_field(nodes[i].bits);
+
+ free(nodes);
+
+}
+
+
+/******************************************************************************
+* *
+* Paramètres : nodes = liste de noeuds détectés dans une routine. *
+* count = taille de cette liste de noeuds à traiter. *
+* *
+* Description : Termine l'initialisation de noeuds trouvés dans une routine. *
+* *
+* Retour : - *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+static void init_mask_for_nodes(dragon_node *nodes, size_t count)
+{
+ size_t i; /* Boucle de parcours */
+
+ for (i = 0; i < count; i++)
+ nodes[i].bits = create_bit_field(count, i > 0);
+
+ set_in_bit_field(nodes[0].bits, 0, 1);
+
+}
+
+
+/******************************************************************************
+* *
+* Paramètres : node = noeud de code à considérer. *
+* first = instruction de départ à renseigner ou NULL. [OUT] *
+* last = instruction d'arrivée à renseigner ou NULL. [OUT] *
+* *
+* Description : Fournit les instructions bornant un noeud de code. *
+* *
+* Retour : - *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+void get_dragon_node_bounding_instructions(dragon_node *node, GArchInstruction **first, GArchInstruction **last)
+{
+ if (first != NULL)
+ *first = node->first;
+
+ if (last != NULL)
+ *last = node->last;
+
+}
+
+
+/******************************************************************************
+* *
+* Paramètres : nodes = liste de noeuds détectés dans une routine. *
+* *
+* Description : Fournit un noeud particulier à partir d'une liste. *
+* *
+* Retour : Noeud ciblé. *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+dragon_node *get_dragon_node(dragon_node *nodes, size_t index)
+{
+ return nodes + index;
+
+}
+
+
+/******************************************************************************
+* *
+* Paramètres : nodes = liste de noeuds détectés dans une routine. *
+* node = noeud ciblé au sein de cette liste. *
+* *
+* Description : Fournit l'indice d'un noeud particulier à partir d'une liste.*
+* *
+* Retour : Indice du noeud ciblé. *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+size_t get_dragon_node_index(dragon_node *nodes, dragon_node *node)
+{
+ return node - nodes;
+
+}
+
+
+/******************************************************************************
+* *
+* Paramètres : nodes = liste de noeuds détectés dans une routine. *
+* count = taille de cette liste de noeuds à parcourir. *
+* final = précise si l'instruction visée est la première. *
+* instr = instruction à retrouver en tant que début de noeud. *
+* *
+* Description : Recherche un noeud selon son intruction de départ. *
+* *
+* Retour : Noeud trouvé ou NULL si aucune trouvaille. *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+dragon_node *find_node_for_instruction(dragon_node *nodes, size_t count, bool final, const GArchInstruction *instr)
+{
+ dragon_node *result; /* Résultat des recherches */
+ const mrange_t *irange; /* Emplacement d'instruction */
+
+ int find_node_from_range(const mrange_t *range, const dragon_node *node)
+ {
+ int status; /* Bilan à retourner */
+ const mrange_t *nrange; /* Emplacement de noeud */
+
+ nrange = g_arch_instruction_get_range(final ? node->last : node->first);
+
+ status = cmp_mrange(range, nrange);
+
+ return status;
+
+ }
+
+ irange = g_arch_instruction_get_range(instr);
+
+ result = bsearch(irange, nodes, count, sizeof(dragon_node), (__compar_fn_t)find_node_from_range);
+
+ return result;
+
+}
+
+
+/******************************************************************************
+* *
+* Paramètres : nodes = liste de noeuds détectés dans une routine. *
+* count = taille de cette liste de noeuds à traiter. *
+* *
+* Description : Détermine toute la chaîne hiérarchique de domination. *
+* *
+* Retour : - *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+void compute_all_dominators(dragon_node *nodes, size_t count)
+{
+ bitfield_t *inter; /* Intersection de dominations */
+ bool changed; /* Note un changement qq part */
+ size_t k; /* Boucle de parcours #1 */
+ dragon_node *node; /* Noeud à traiter */
+ dragon_node *predecessor; /* Noeud prédécesseur direct */
+ GArchInstruction **srcs; /* Instructions d'origine */
+ InstructionLinkType *types; /* Type de lien entre instr. */
+ size_t scount; /* Nombre de liens de source */
+ size_t i; /* Boucle de parcours #2 */
+
+ inter = create_bit_field(count, false);
+
+ do
+ {
+ changed = false;
+
+ for (k = 1; k < count; k++)
+ {
+ node = &nodes[k];
+
+ set_all_in_bit_field(inter);
+
+ scount = g_arch_instruction_get_sources(node->first, &srcs, &types);
+ assert(scount > 0);
+
+ for (i = 0; i < scount; i++)
+ switch (types[i])
+ {
+ case ILT_EXEC_FLOW:
+ case ILT_JUMP:
+ case ILT_CASE_JUMP:
+ case ILT_JUMP_IF_TRUE:
+ case ILT_JUMP_IF_FALSE:
+
+ predecessor = find_node_for_instruction(nodes, count, true, srcs[i]);
+
+
+ printf(" -- finding pred @ 0x%08x -> 0x%08x :: %p\n",
+ (unsigned int)g_arch_instruction_get_range(node->first)->addr.virtual,
+ (unsigned int)g_arch_instruction_get_range(srcs[i])->addr.virtual,
+ predecessor);
+
+
+
+ if (predecessor == NULL) break;
+
+ and_bit_field(inter, predecessor->bits);
+ break;
+
+ default:
+ break;
+
+ }
+
+ set_in_bit_field(inter, k, 1);
+
+ if (!is_bit_field_equal_to(node->bits, inter))
+ {
+ copy_bit_field(node->bits, inter);
+ changed = true;
+ }
+
+ }
+
+ }
+ while (changed);
+
+ delete_bit_field(inter);
+
+}
+
+
+/******************************************************************************
+* *
+* Paramètres : node = noeud représentant une portion de code à consulter. *
+* *
+* Description : Fournit la liste des noeuds dominés par un noeud. *
+* *
+* Retour : Champ de bits en place. *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+const bitfield_t *get_domination_bits(const dragon_node *node)
+{
+ return node->bits;
+
+}
+
+
+
+
+
+
+/* ---------------------------------------------------------------------------------- */
+/* ENCAPSULATION DES NOEUDS */
+/* ---------------------------------------------------------------------------------- */
+
+
+/******************************************************************************
+* *
+* Paramètres : proc = ensemble d'instructions à parcourir. *
+* coverage = zone de couverture où rechercher des instructions.*
+* range = zone de couverture de la routine analysée. *
+* start = adresse du début de l'analyse. *
+* *
+* Description : Attaque la complexité d'un code en créant des noeuds. *
+* *
+* Retour : Définition d'un complexe de noeuds établis. *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+dragon_knight *begin_dragon_knight(const GArchProcessor *proc, const instr_coverage *coverage, const mrange_t *range, const vmpa2t *start)
+{
+ dragon_knight *result; /* Données à retourner */
+ dragon_node *nodes; /* Noeuds mis en place */
+ size_t count; /* Nombre de ces noeuds */
+
+ result = NULL;
+
+ nodes = create_dragon_nodes(proc, coverage, range, start, &count);
+
+ if (nodes != NULL)
+ {
+ init_mask_for_nodes(nodes, count);
+
+ result = (dragon_knight *)calloc(1, sizeof(dragon_knight));
+
+ result->nodes = nodes;
+ result->count = count;
+
+ }
+
+ return result;
+
+}
+
+
+/******************************************************************************
+* *
+* Paramètres : knight = données représentant une complexité traitée. *
+* *
+* Description : Supprime de la mémoire les données d'une complexité de code. *
+* *
+* Retour : - *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+void end_dragon_knight(dragon_knight *knight)
+{
+ delete_dragon_nodes(knight->nodes, knight->count);
+
+ free(knight);
+
+}
+
+
+/******************************************************************************
+* *
+* Paramètres : knight = données représentant une complexité à considérer. *
+* nodes = noeuds de code associés à récupérer. [OUT] *
+* count = taille de cette liste de noeuds. [OUT] *
+* *
+* Description : Fournit les éléments utiles à un traitement de blocs de code.*
+* *
+* Retour : - *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+void get_dragon_knight_content(dragon_knight *knight, dragon_node **nodes, size_t *count)
+{
+ *nodes = knight->nodes;
+ *count = knight->count;
+
+}
diff --git a/src/analysis/disass/dragon.h b/src/analysis/disass/dragon.h
new file mode 100644
index 0000000..c6f6fd5
--- /dev/null
+++ b/src/analysis/disass/dragon.h
@@ -0,0 +1,81 @@
+
+/* Chrysalide - Outil d'analyse de fichiers binaires
+ * dragon.h - prototypes pour les capacités apportées par la lecture du livre du dragon
+ *
+ * Copyright (C) 2016 Cyrille Bagard
+ *
+ * This file is part of Chrysalide.
+ *
+ * OpenIDA is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * OpenIDA is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with Foobar. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+
+#ifndef _ANALYSIS_DISASS_DRAGON_H
+#define _ANALYSIS_DISASS_DRAGON_H
+
+
+#include "../../arch/processor.h"
+#include "../../common/bits.h"
+
+
+
+/* -------------------------- DECOUPAGES DE CODE EN NOEUDS -------------------------- */
+
+
+/* Description de noeud, en référence à "Compilers: Principles, Techniques, and Tools" */
+typedef struct _dragon_node dragon_node;
+
+
+/* Fournit les instructions bornant un noeud de code. */
+void get_dragon_node_bounding_instructions(dragon_node *, GArchInstruction **, GArchInstruction **);
+
+/* Fournit un noeud particulier à partir d'une liste. */
+dragon_node *get_dragon_node(dragon_node *, size_t);
+
+/* Fournit l'indice d'un noeud particulier à partir d'une liste. */
+size_t get_dragon_node_index(dragon_node *, dragon_node *);
+
+/* Recherche un noeud selon son intruction de départ. */
+dragon_node *find_node_for_instruction(dragon_node *, size_t, bool, const GArchInstruction *);
+
+/* Détermine toute la chaîne hiérarchique de domination. */
+void compute_all_dominators(dragon_node *, size_t);
+
+/* Fournit la liste des noeuds dominés par un noeud. */
+const bitfield_t *get_domination_bits(const dragon_node *);
+
+
+
+
+
+
+/* ---------------------------- ENCAPSULATION DES NOEUDS ---------------------------- */
+
+
+/* Concentration de tous les efforts */
+typedef struct _dragon_knight dragon_knight;
+
+
+/* Attaque la complexité d'un code en créant des noeuds. */
+dragon_knight *begin_dragon_knight(const GArchProcessor *, const instr_coverage *, const mrange_t *, const vmpa2t *);
+
+/* Supprime de la mémoire les données d'une complexité de code. */
+void end_dragon_knight(dragon_knight *);
+
+/* Fournit les éléments utiles à un traitement de blocs de code. */
+void get_dragon_knight_content(dragon_knight *, dragon_node **, size_t *);
+
+
+
+#endif /* _ANALYSIS_DISASS_DRAGON_H */
diff --git a/src/analysis/disass/loop.c b/src/analysis/disass/loop.c
index 94916f7..dd0b661 100644
--- a/src/analysis/disass/loop.c
+++ b/src/analysis/disass/loop.c
@@ -28,39 +28,14 @@
#include <malloc.h>
-#include "../../common/bits.h"
-
-
-
-/* Description de noeud, en référence à "Compilers: Principles, Techniques, and Tools" */
-typedef struct _dragon_node
-{
- GArchInstruction *first; /* Arrivée d'un lien (début) */
- GArchInstruction *last; /* Départ d'un lien (fin) */
-
- bitfield_t *bits; /* Représentation par masque */
-
-} dragon_node;
+#include "dragon.h"
-/* Définition des blocs d'allocation */
-#define NODE_ALLOC_SIZE 100
-/* Dénombre le nombre de noeuds présents dans une routine. */
-static dragon_node *create_dragon_nodes(const GArchProcessor *, const instr_coverage *, const mrange_t *, const vmpa2t *, size_t *);
-/* Termine l'initialisation de noeuds trouvés dans une routine. */
-static void define_mask_for_nodes(dragon_node *, size_t);
-/* Supprime de la mémoire tous les noeuds détectés. */
-static void delete_dragon_nodes(dragon_node *, size_t);
-/* Recherche un noeud selon son intruction de départ. */
-static dragon_node *find_node_for_instruction(dragon_node *, size_t, bool, const GArchInstruction *);
-
-/* Détermine toute la chaîne hiérarchique de domination. */
-static void compute_all_dominators(dragon_node *, size_t);
/* Matérialise les liens de retour arrière en tant que boucles. */
static void detect_back_edges(dragon_node *, size_t);
@@ -70,294 +45,6 @@ static void track_loops_in_code(const GArchProcessor *, const instr_coverage *,
-/******************************************************************************
-* *
-* Paramètres : proc = ensemble d'instructions à parcourir. *
-* coverage = zone de couverture où rechercher des instructions.*
-* range = zone de couverture de la routine analysée. *
-* start = adresse du début de l'analyse. *
-* count = taille de la liste de noeuds retournés. [OUT] *
-* *
-* Description : Dénombre le nombre de noeuds présents dans une routine. *
-* *
-* Retour : Liste de noeuds initialisés de façon incomplète. *
-* *
-* Remarques : - *
-* *
-******************************************************************************/
-
-static dragon_node *create_dragon_nodes(const GArchProcessor *proc, const instr_coverage *coverage, const mrange_t *range, const vmpa2t *start, size_t *count)
-{
- dragon_node *result; /* Liste à créer et renvoyer */
- size_t allocated; /* Dimensionnement en mémoire */
- GArchInstruction *last; /* Mémorisation du passé */
- GArchInstruction *iter; /* Boucle de parcours */
- const mrange_t *irange; /* Emplacement d'instruction */
- InstructionLinkType *types; /* Type de lien entre instr. */
- size_t scount; /* Nombre de liens de dest. */
- size_t i; /* Boucle de parcours */
- dragon_node *new; /* Nouvel élément à créer */
-
- result = NULL;
- *count = 0;
-
- allocated = 0;
-
- for (last = NULL, iter = g_arch_processor_find_covered_instr_by_address(proc, coverage, start);
- iter != NULL;
- last = iter, iter = g_arch_instruction_get_next_iter(iter /* FIXME : list*/, iter, ~0))
- {
- /* L'instruction sort-elle des clous ? */
-
- irange = g_arch_instruction_get_range(iter);
-
- if (!mrange_contains_mrange(range, irange))
- break;
-
- /* Analyse des sources */
-
- if (result == NULL)
- {
- (*count)++;
-
- if (*count >= allocated)
- {
- allocated += NODE_ALLOC_SIZE;
- result = (dragon_node *)realloc(result, allocated * sizeof(dragon_node));
- }
-
- new = &result[*count - 1];
-
- new->first = iter;
-
- }
- else
- {
- scount = g_arch_instruction_get_sources(iter, NULL, &types);
- if (scount == 0) continue;
-
- for (i = 0; i < scount; i++)
- switch (types[i])
- {
- case ILT_EXEC_FLOW:
- case ILT_JUMP:
- case ILT_CASE_JUMP:
- case ILT_JUMP_IF_TRUE:
- case ILT_JUMP_IF_FALSE:
-
- if (*count > 0)
- result[*count - 1].last = last;
-
- (*count)++;
- i = scount;
-
- if (*count >= allocated)
- {
- allocated += NODE_ALLOC_SIZE;
- result = (dragon_node *)realloc(result, allocated * sizeof(dragon_node));
- }
-
- new = &result[*count - 1];
-
- new->first = iter;
-
- break;
-
- default:
- break;
-
- }
-
- }
-
- }
-
- if (*count > 0)
- result[*count - 1].last = last;
-
- return result;
-
-}
-
-
-/******************************************************************************
-* *
-* Paramètres : nodes = liste de noeuds détectés dans une routine. *
-* count = taille de cette liste de noeuds à traiter. *
-* *
-* Description : Termine l'initialisation de noeuds trouvés dans une routine. *
-* *
-* Retour : - *
-* *
-* Remarques : - *
-* *
-******************************************************************************/
-
-static void define_mask_for_nodes(dragon_node *nodes, size_t count)
-{
- size_t i; /* Boucle de parcours */
-
- for (i = 0; i < count; i++)
- nodes[i].bits = create_bit_field(count, i > 0);
-
- set_in_bit_field(nodes[0].bits, 0, 1);
-
-}
-
-
-/******************************************************************************
-* *
-* Paramètres : nodes = liste de noeuds détectés dans une routine. *
-* count = taille de cette liste de noeuds à traiter. *
-* *
-* Description : Supprime de la mémoire tous les noeuds détectés. *
-* *
-* Retour : - *
-* *
-* Remarques : - *
-* *
-******************************************************************************/
-
-static void delete_dragon_nodes(dragon_node *nodes, size_t count)
-{
- size_t i; /* Boucle de parcours */
-
- for (i = 0; i < count; i++)
- delete_bit_field(nodes[i].bits);
-
- free(nodes);
-
-}
-
-
-/******************************************************************************
-* *
-* Paramètres : nodes = liste de noeuds détectés dans une routine. *
-* count = taille de cette liste de noeuds à parcourir. *
-* final = précise si l'instruction visée est la première. *
-* instr = instruction à retrouver en tant que début de noeud. *
-* *
-* Description : Recherche un noeud selon son intruction de départ. *
-* *
-* Retour : Noeud trouvé ou NULL si aucune trouvaille. *
-* *
-* Remarques : - *
-* *
-******************************************************************************/
-
-static dragon_node *find_node_for_instruction(dragon_node *nodes, size_t count, bool final, const GArchInstruction *instr)
-{
- dragon_node *result; /* Résultat des recherches */
- const mrange_t *irange; /* Emplacement d'instruction */
-
- int find_node_from_range(const mrange_t *range, const dragon_node *node)
- {
- int status; /* Bilan à retourner */
- const mrange_t *nrange; /* Emplacement de noeud */
-
- nrange = g_arch_instruction_get_range(final ? node->last : node->first);
-
- status = cmp_mrange(range, nrange);
-
- return status;
-
- }
-
- irange = g_arch_instruction_get_range(instr);
-
- result = bsearch(irange, nodes, count, sizeof(dragon_node), (__compar_fn_t)find_node_from_range);
-
- return result;
-
-}
-
-
-/******************************************************************************
-* *
-* Paramètres : nodes = liste de noeuds détectés dans une routine. *
-* count = taille de cette liste de noeuds à traiter. *
-* *
-* Description : Détermine toute la chaîne hiérarchique de domination. *
-* *
-* Retour : - *
-* *
-* Remarques : - *
-* *
-******************************************************************************/
-
-static void compute_all_dominators(dragon_node *nodes, size_t count)
-{
- bitfield_t *inter; /* Intersection de dominations */
- bool changed; /* Note un changement qq part */
- size_t k; /* Boucle de parcours #1 */
- dragon_node *node; /* Noeud à traiter */
- dragon_node *predecessor; /* Noeud prédécesseur direct */
- GArchInstruction **srcs; /* Instructions d'origine */
- InstructionLinkType *types; /* Type de lien entre instr. */
- size_t scount; /* Nombre de liens de source */
- size_t i; /* Boucle de parcours #2 */
-
- inter = create_bit_field(count, false);
-
- do
- {
- changed = false;
-
- for (k = 1; k < count; k++)
- {
- node = &nodes[k];
-
- set_all_in_bit_field(inter);
-
- scount = g_arch_instruction_get_sources(node->first, &srcs, &types);
- assert(scount > 0);
-
- for (i = 0; i < scount; i++)
- switch (types[i])
- {
- case ILT_EXEC_FLOW:
- case ILT_JUMP:
- case ILT_CASE_JUMP:
- case ILT_JUMP_IF_TRUE:
- case ILT_JUMP_IF_FALSE:
-
- predecessor = find_node_for_instruction(nodes, count, true, srcs[i]);
-
-
- printf(" -- finding pred @ 0x%08x -> 0x%08x :: %p\n",
- (unsigned int)g_arch_instruction_get_range(node->first)->addr.virtual,
- (unsigned int)g_arch_instruction_get_range(srcs[i])->addr.virtual,
- predecessor);
-
-
-
- if (predecessor == NULL) break;
-
- and_bit_field(inter, predecessor->bits);
- break;
-
- default:
- break;
-
- }
-
- set_in_bit_field(inter, k, 1);
-
- if (!is_bit_field_equal_to(node->bits, inter))
- {
- copy_bit_field(node->bits, inter);
- changed = true;
- }
-
- }
-
- }
- while (changed);
-
- delete_bit_field(inter);
-
-}
-
/******************************************************************************
@@ -377,6 +64,8 @@ static void detect_back_edges(dragon_node *nodes, size_t count)
{
size_t k; /* Boucle de parcours #1 */
dragon_node *node; /* Noeud à traiter */
+ const bitfield_t *dominators; /* Liste de dominateurs */
+ GArchInstruction *last; /* Instruction finale de noeud */
GArchInstruction **dests; /* Instr. visée par une autre */
InstructionLinkType *types; /* Type de lien entre lignes */
size_t dcount; /* Nombre de liens de dest. */
@@ -390,24 +79,33 @@ static void detect_back_edges(dragon_node *nodes, size_t count)
for (k = 0; k < count; k++)
{
- node = &nodes[k];
+ GArchInstruction *first;
+
+ node = get_dragon_node(nodes, k);
+
+ dominators = get_domination_bits(node);
+
+ get_dragon_node_bounding_instructions(node, &first, &last);
+
printf("#[ node %zu ]# @ 0x%08x / 0x%08x - mask = 0x%08lx\n", k,
- (unsigned int)g_arch_instruction_get_range(node->first)->addr.virtual,
- (unsigned int)g_arch_instruction_get_range(node->last)->addr.virtual,
- gfw(node->bits));
+ (unsigned int)g_arch_instruction_get_range(first)->addr.virtual,
+ (unsigned int)g_arch_instruction_get_range(last)->addr.virtual,
+ gfw(dominators));
}
printf("\n");
-
-
for (k = 1; k < count; k++)
{
- node = &nodes[k];
+ node = get_dragon_node(nodes, k);
+
+ dominators = get_domination_bits(node);
- dcount = g_arch_instruction_get_destinations(node->last, &dests, &types, NULL);
+ get_dragon_node_bounding_instructions(node, NULL, &last);
+
+ dcount = g_arch_instruction_get_destinations(last, &dests, &types, NULL);
if (dcount == 0) continue;
for (i = 0; i < dcount; i++)
@@ -422,17 +120,17 @@ static void detect_back_edges(dragon_node *nodes, size_t count)
target = find_node_for_instruction(nodes, count, false, dests[i]);
if (target == NULL) break;
- id = (target - nodes);
+ id = get_dragon_node_index(nodes, target);
- if (test_in_bit_field(node->bits, id, 1))
+ if (test_in_bit_field(dominators, id, 1))
{
printf("BACKEDGE :: 0x%08lx -> 0x%08lx\n",
- (unsigned int)g_arch_instruction_get_range(node->last)->addr.virtual,
+ (unsigned int)g_arch_instruction_get_range(last)->addr.virtual,
(unsigned int)g_arch_instruction_get_range(dests[i])->addr.virtual);
- /* status = */g_arch_instruction_change_link(node->last, dests[i], types[i], ILT_LOOP);
+ /* status = */g_arch_instruction_change_link(last, dests[i], types[i], ILT_LOOP);
}
@@ -468,25 +166,29 @@ static void detect_back_edges(dragon_node *nodes, size_t count)
static void track_loops_in_code(const GArchProcessor *proc, const instr_coverage *coverage, const mrange_t *range, const vmpa2t *start, memfield_t *flow)
{
+ dragon_knight *knight; /* Complexité de code posée */
dragon_node *nodes; /* Liste des noeuds détectés */
size_t count; /* Taille de cette liste */
- nodes = create_dragon_nodes(proc, coverage, range, start, &count);
+ knight = begin_dragon_knight(proc, coverage, range, start);
+ if (knight == NULL) return;
- if (nodes == NULL) return;
+ assert(knight != NULL);
- assert(nodes != NULL);
- printf("nodes count :: %d\n", (int)count);
- define_mask_for_nodes(nodes, count);
+ get_dragon_knight_content(knight, &nodes, &count);
+
+
+ printf("nodes count :: %d\n", (int)count);
compute_all_dominators(nodes, count);
detect_back_edges(nodes, count);
- delete_dragon_nodes(nodes, count);
+
+ end_dragon_knight(knight);
}
diff --git a/src/common/bits.c b/src/common/bits.c
index b08dcb4..90cb098 100644
--- a/src/common/bits.c
+++ b/src/common/bits.c
@@ -460,7 +460,7 @@ void or_bit_field(bitfield_t *dest, const bitfield_t *src)
* *
******************************************************************************/
-bool test_in_bit_field(bitfield_t *field, size_t first, size_t count)
+bool test_in_bit_field(const bitfield_t *field, size_t first, size_t count)
{
bool result; /* Valeur retrouvée à renvoyer */
size_t last; /* Point d'arrêt de la boucle */
diff --git a/src/common/bits.h b/src/common/bits.h
index 074aac4..6d8ea5b 100644
--- a/src/common/bits.h
+++ b/src/common/bits.h
@@ -70,7 +70,7 @@ void and_bit_field(bitfield_t *, const bitfield_t *);
void or_bit_field(bitfield_t *, const bitfield_t *);
/* Détermine si un bit est à 1 dans un champ de bits. */
-bool test_in_bit_field(bitfield_t *, size_t, size_t);
+bool test_in_bit_field(const bitfield_t *, size_t, size_t);
/* Indique si deux champs de bits sont identiques ou non. */
bool is_bit_field_equal_to(const bitfield_t *, const bitfield_t *);
--
cgit v0.11.2-87-g4458