Handled irreducible loops without blocking.

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 */