summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/analysis/disass/dragon.c2
-rw-r--r--src/analysis/disass/loop.c438
-rw-r--r--src/analysis/disass/loop.h4
-rw-r--r--src/analysis/disass/routines.c4
4 files changed, 397 insertions, 51 deletions
diff --git a/src/analysis/disass/dragon.c b/src/analysis/disass/dragon.c
index eb91ad1..89dc784 100644
--- a/src/analysis/disass/dragon.c
+++ b/src/analysis/disass/dragon.c
@@ -817,6 +817,8 @@ GBlockList *translate_dragon_knight(const dragon_knight *knight, GLoadedBinary *
get_dragon_knight_content(knight, &nodes, &count);
+ compute_all_dominators(nodes, count);
+
result = g_block_list_new(count);
for (i = 0; i < count; i++)
diff --git a/src/analysis/disass/loop.c b/src/analysis/disass/loop.c
index b41e6b2..9e964e5 100644
--- a/src/analysis/disass/loop.c
+++ b/src/analysis/disass/loop.c
@@ -24,18 +24,140 @@
#include "loop.h"
+#include <assert.h>
+#include <malloc.h>
-/* Matérialise les liens de retour arrière en tant que boucles. */
-static void detect_back_edges(dragon_node *, size_t);
+
+#include "block.h"
+
+
+
+/**
+ * Adaptation de l'algorithme : "A New Algorithm for Identifying Loops in Decompilation".
+ */
+
+
+
+/* Informations associées à un bloc */
+typedef struct _bblock_info_t
+{
+ bool traversed; /* Etat du traitement */
+ unsigned int dfsp_pos; /* Indice dans un chemin */
+ struct _bblock_info_t *iloop_header; /* Pointeur de bloc d'entête */
+
+ bool irreducible; /* Détection d'irreducible */
+
+} bblock_info_t;
+
+/* Informations associées à un lien */
+typedef struct _bblock_link_t
+{
+ GCodeBlock *linked; /* Destination du bloc visé */
+ InstructionLinkType type; /* Type de liaison */
+ bblock_info_t *info; /* Informations sur ce bloc */
+
+} bblock_link_t;
+
+
+/* Détermine les liens vers des blocs successeurs d'un bloc. */
+static bblock_link_t *get_block_links(GCodeBlock *, bblock_info_t *, bool, size_t *);
+
+#define get_block_predecessors(b, i, c) \
+ get_block_links(b, i, false, c)
+
+#define get_block_successors(b, i, c) \
+ get_block_links(b, i, true, c)
+
+/* Libère de la mémoire les liens vers des blocs successeurs. */
+static void delete_block_links(bblock_link_t *, size_t);
+
+/* Marque un bloc comme étant un entête de boucle. */
+static void tag_loop_head(bblock_info_t *, bblock_info_t *);
+
+/* Parcourt une arborescence de blocs à la recherche de boucles. */
+static bblock_info_t *traverse_basic_blocks_dfs(bblock_info_t *, GBlockList *, bblock_info_t *, unsigned int);
+
+/* Définit les boucles entre un ensemble de blocs basiques. */
+static void define_basic_blocks_loops(GBlockList *list, bblock_info_t *);
/******************************************************************************
* *
-* Paramètres : nodes = liste de noeuds détectés dans une routine. *
-* count = taille de cette liste de noeuds à traiter. *
+* Paramètres : block = bloc de code, basique, à considérer. *
+* info = informations complémentaires quant aux blocs. *
+* succ = true si les successeurs sont visés, false sinon. *
+* count = nombre de liens effectivement utiles. [OUT] *
+* *
+* Description : Détermine les liens vers des blocs successeurs d'un bloc. *
+* *
+* Retour : Liste de liens retrouvés ou NULL si vraiment aucun. *
* *
-* Description : Matérialise les liens de retour arrière en tant que boucles. *
+* Remarques : - *
+* *
+******************************************************************************/
+
+static bblock_link_t *get_block_links(GCodeBlock *block, bblock_info_t *info, bool succ, size_t *count)
+{
+ bblock_link_t *result; /* Liste à retourner */
+ size_t allocated; /* Nombre d'éléments au maximum*/
+ block_link_t *links; /* Liens associés au bloc */
+ size_t i; /* Boucle de parcours */
+ bblock_link_t *new; /* Mémorisation de ce lien */
+
+ if (succ)
+ links = g_code_block_get_destinations(block, &allocated);
+ else
+ links = g_code_block_get_sources(block, &allocated);
+
+ result = malloc(allocated * sizeof(bblock_link_t));
+
+ *count = 0;
+
+ for (i = 0; i < allocated; i++)
+ {
+ switch (links[i].type)
+ {
+ case ILT_EXEC_FLOW:
+ case ILT_JUMP:
+ case ILT_CASE_JUMP:
+ case ILT_JUMP_IF_TRUE:
+ case ILT_JUMP_IF_FALSE:
+
+ new = &result[(*count)++];
+
+ new->linked = links[i].linked;
+ g_object_ref(G_OBJECT(new->linked));
+
+ new->type = links[i].type;
+
+ new->info = info + g_code_block_get_index(new->linked);
+
+ break;
+
+ default:
+ break;
+
+ }
+
+ unref_block_link(&links[i]);
+
+ }
+
+ if (links != NULL)
+ free(links);
+
+ return result;
+
+}
+
+
+/******************************************************************************
+* *
+* Paramètres : links = liste de liens retrouvés ou NULL si vraiment aucun. *
+* count = nombre de liens effectivement utiles. *
+* *
+* Description : Libère de la mémoire les liens vers des blocs successeurs. *
* *
* Retour : - *
* *
@@ -43,61 +165,275 @@ static void detect_back_edges(dragon_node *, size_t);
* *
******************************************************************************/
-static void detect_back_edges(dragon_node *nodes, size_t count)
+static void delete_block_links(bblock_link_t *links, 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 */
- size_t dcount; /* Nombre de liens de dest. */
- size_t i; /* Boucle de parcours #2 */
- const instr_link_t *dest; /* Instr. visée par une autre */
- dragon_node *target; /* Noeud référence à tester */
- size_t id; /* Indice du bit associé */
-
- for (k = 0; k < count; k++)
+ size_t i; /* Boucle de parcours */
+
+ for (i = 0; i < count; i++)
+ g_object_unref(G_OBJECT(links[i].linked));
+
+ if (links != NULL)
+ free(links);
+
+}
+
+
+/******************************************************************************
+* *
+* Paramètres : blk = bloc à mettre à jour. *
+* hdr = bloc d'entête à mémoriser. *
+* *
+* Description : Marque un bloc comme étant un entête de boucle. *
+* *
+* Retour : - *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+static void tag_loop_head(bblock_info_t *blk, bblock_info_t *hdr)
+{
+ bblock_info_t *cur1; /* Boucle de parcours #1 */
+ bblock_info_t *cur2; /* Boucle de parcours #2 */
+ bblock_info_t *ih; /* Boucle de parcours #3 */
+
+ if (blk == hdr || hdr == NULL)
+ goto done;
+
+ cur1 = blk;
+ cur2 = hdr;
+
+ while (cur1->iloop_header != NULL)
{
- node = get_dragon_node(nodes, k);
+ ih = cur1->iloop_header;
+
+ if (ih == cur2)
+ goto done;
+
+ if (ih->dfsp_pos < cur2->dfsp_pos)
+ {
+ cur1->iloop_header = cur2;
+ cur1 = cur2;
+ cur2 = ih;
+ }
+
+ else
+ cur1 = ih;
- dominators = get_domination_bits(node);
+ }
- get_dragon_node_bounding_instructions(node, NULL, &last);
+ cur1->iloop_header = cur2;
- g_arch_instruction_lock_dest(last);
- dcount = g_arch_instruction_count_destinations(last);
+ done:
- for (i = 0; i < dcount; i++)
+ ;
+
+}
+
+
+/******************************************************************************
+* *
+* Paramètres : root = élément racine à considérer. *
+* list = liste de blocs de code à consulter. *
+* info = informations complémentaires quant aux blocs. *
+* pos = position dans le chemin courant. *
+* *
+* Description : Parcourt une arborescence de blocs à la recherche de boucles.*
+* *
+* Retour : Entête de boucle trouvée ou NULL. *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+static bblock_info_t *traverse_basic_blocks_dfs(bblock_info_t *root, GBlockList *list, bblock_info_t *info, unsigned int pos)
+{
+ GCodeBlock *block; /* Bloc basique courant */
+ bblock_link_t *links; /* Liste de successeurs */
+ size_t count; /* Taille de cette liste */
+ size_t i; /* Boucle de parcours */
+ bblock_info_t *succ; /* Successeur à traiter */
+ bblock_info_t *nh; /* Nouvel entête de boucle */
+ bblock_info_t *h; /* Entête de boucle */
+
+ root->traversed = true;
+ root->dfsp_pos = pos;
+
+ block = g_block_list_get_block(list, root - info);
+
+ links = get_block_successors(block, info, &count);
+
+ for (i = 0; i < count; i++)
+ {
+ succ = links[i].info;
+
+ /* Cas A : bloc jamais traversé */
+ if (!succ->traversed)
{
- dest = g_arch_instruction_get_destination(last, i);
+ nh = traverse_basic_blocks_dfs(succ, list, info, pos + 1);
+ tag_loop_head(root, nh);
+ }
- switch (dest->type)
+ else
+ {
+ /* Le successeur est dans DFSP(root) */
+ if (succ->dfsp_pos > 0)
{
- case ILT_EXEC_FLOW:
- case ILT_JUMP:
- case ILT_CASE_JUMP:
- case ILT_JUMP_IF_TRUE:
- case ILT_JUMP_IF_FALSE:
+ /* Cas B : on le marque en tant qu'entête de boucle */
+ tag_loop_head(root, succ);
+ }
+
+ /* Cas C : on ne fait rien */
+ else if (succ->iloop_header == NULL)
+ {
+
+ }
- target = find_node_for_instruction(nodes, count, false, dest->linked);
- if (target == NULL) break;
+ else
+ {
+ h = succ->iloop_header;
+
+ /* h est dans DFSP(root) */
+ if (h->dfsp_pos > 0)
+ {
+ /* Cas D */
+ tag_loop_head(root, h);
+ }
+
+ /* h n'est pas dans DFSP(root) */
+ else
+ {
+ /* Cas E : réentrance */
- id = get_dragon_node_index(nodes, target);
+ succ->irreducible = true;
- if (test_in_bit_field(dominators, id))
- g_arch_instruction_change_link(last, dest->linked, dest->type, ILT_LOOP);
+ while (h->iloop_header != NULL)
+ {
+ h = h->iloop_header;
- break;
+ /* h est dans DFSP(root) */
+ if (h->dfsp_pos > 0)
+ {
+ tag_loop_head(root, h);
+ break;
+ }
- default:
- break;
+ }
+
+ }
}
- unref_instr_link(dest);
+ }
+
+ }
+
+ delete_block_links(links, count);
+
+ g_object_unref(G_OBJECT(block));
+
+ /* Efface la position du bloc courant dans le chemin */
+ root->dfsp_pos = 0;
+
+ return root->iloop_header;
+
+}
+
+
+/******************************************************************************
+* *
+* Paramètres : list = liste de blocs de code à consulter. *
+* info = informations complémentaires quant aux blocs. *
+* *
+* Description : Définit les boucles entre un ensemble de blocs basiques. *
+* *
+* Retour : - *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+static void define_basic_blocks_loops(GBlockList *list, bblock_info_t *info)
+{
+ size_t available; /* Quantité de blocs présents */
+ size_t i; /* Boucle de parcours #1 */
+ bblock_info_t *iter; /* Boucle de parcours #2 */
+ GCodeBlock *block; /* Bloc basique courant */
+ bblock_link_t *links; /* Liste de successeurs */
+ size_t count; /* Taille de cette liste */
+ size_t k; /* Boucle de parcours #3 */
+ GArchInstruction *first; /* Instruction initiale de bloc*/
+ GArchInstruction *last; /* Instruction finale de bloc */
+#ifndef NDEBUG
+ bool status; /* Bilan du changement */
+#endif
+
+ available = g_block_list_count_blocks(list);
+
+ for (i = 0, iter = info; i < available; i++, iter++)
+ {
+ block = g_block_list_get_block(list, i);
+
+ if (iter->irreducible)
+ {
+ links = get_block_predecessors(block, info, &count);
+
+
+ for (k = 0; k < count; k++)
+ if (links[k].info->iloop_header == iter->iloop_header)
+ {
+ g_basic_block_get_boundaries(G_BASIC_BLOCK(links[k].linked), NULL, &last);
+ g_basic_block_get_boundaries(G_BASIC_BLOCK(block), &first, NULL);
+
+ g_arch_instruction_lock_dest(last);
+
+#ifndef NDEBUG
+ status = g_arch_instruction_change_link(last, first, links[k].type, ILT_LOOP);
+ assert(status);
+#else
+ g_arch_instruction_change_link(last, first, links[k].type, ILT_LOOP);
+#endif
+
+ g_arch_instruction_unlock_dest(last);
+
+ g_object_unref(G_OBJECT(first));
+ g_object_unref(G_OBJECT(last));
+
+ }
+
+ }
+
+ else
+ {
+ links = get_block_successors(block, info, &count);
+
+ for (k = 0; k < count; k++)
+ if (links[k].info == iter->iloop_header)
+ {
+ g_basic_block_get_boundaries(G_BASIC_BLOCK(block), NULL, &last);
+ g_basic_block_get_boundaries(G_BASIC_BLOCK(links[k].linked), &first, NULL);
+
+ g_arch_instruction_lock_dest(last);
+
+#ifndef NDEBUG
+ status = g_arch_instruction_change_link(last, first, links[k].type, ILT_LOOP);
+ assert(status);
+#else
+ g_arch_instruction_change_link(last, first, links[k].type, ILT_LOOP);
+#endif
+
+ g_arch_instruction_unlock_dest(last);
+
+ g_object_unref(G_OBJECT(first));
+ g_object_unref(G_OBJECT(last));
+
+ }
}
- g_arch_instruction_unlock_dest(last);
+ delete_block_links(links, count);
+
+ g_object_unref(G_OBJECT(block));
}
@@ -106,7 +442,7 @@ static void detect_back_edges(dragon_node *nodes, size_t count)
/******************************************************************************
* *
-* Paramètres : knight = informations quant à la complexité gérée du code. *
+* Paramètres : list = liste de blocs de code à consulter. *
* *
* Description : Détecte les boucles dans du code machine. *
* *
@@ -116,15 +452,23 @@ static void detect_back_edges(dragon_node *nodes, size_t count)
* *
******************************************************************************/
-void detect_loops_in_code(dragon_knight *knight)
+void detect_loops_in_basic_blocks(GBlockList *list)
{
- dragon_node *nodes; /* Liste des noeuds détectés */
- size_t count; /* Taille de cette liste */
+ size_t count; /* Quantité de blocs présents */
+ bblock_info_t *info; /* Informations supplémentaires*/
- get_dragon_knight_content(knight, &nodes, &count);
+ count = g_block_list_count_blocks(list);
- compute_all_dominators(nodes, count);
+ if (count > 1)
+ {
+ info = calloc(count, sizeof(bblock_info_t));
+
+ traverse_basic_blocks_dfs(&info[0], list, info, 1);
+
+ define_basic_blocks_loops(list, info);
- detect_back_edges(nodes, count);
+ free(info);
+
+ }
}
diff --git a/src/analysis/disass/loop.h b/src/analysis/disass/loop.h
index 4e8ccb0..c8ef0e8 100644
--- a/src/analysis/disass/loop.h
+++ b/src/analysis/disass/loop.h
@@ -25,12 +25,12 @@
#define _ANALYSIS_DISASS_LOOP_H
-#include "dragon.h"
+#include "../block.h"
/* Détecte les boucles dans du code machine. */
-void detect_loops_in_code(dragon_knight *);
+void detect_loops_in_basic_blocks(GBlockList *);
diff --git a/src/analysis/disass/routines.c b/src/analysis/disass/routines.c
index d260bad..d288fc0 100644
--- a/src/analysis/disass/routines.c
+++ b/src/analysis/disass/routines.c
@@ -400,12 +400,12 @@ void g_routines_study_handle_blocks(GRoutinesStudy *study, GBinRoutine *routine,
/* Traitement par blocs */
- detect_loops_in_code(knight);
-
blocks = translate_dragon_knight(knight, study->binary);
g_binary_routine_set_basic_blocks(routine, blocks);
+ detect_loops_in_basic_blocks(blocks);
+
rank_routine_blocks(routine);
/* Nettoyage final */
generated by cgit v0.11.2-87-g4458 at 2024-12-25 08:16:29 (GMT)