Reduced the quantity of used variables in decompiled code.

git-svn-id: svn://svn.gna.org/svn/chrysalide/trunk@332 abbe820e-26c8-41b2-8c08-b7b2b41f8b0a

1 files changed, 382 insertions, 13 deletions

diff --git a/src/analysis/decomp/reduce.c b/src/analysis/decomp/reduce.c
index 926650d..2d6fce3 100644
--- a/src/analysis/decomp/reduce.c
+++ b/src/analysis/decomp/reduce.c
@@ -2,7 +2,7 @@
 /* OpenIDA - Outil d'analyse de fichiers binaires
  * reduce.c - réduction de l'usage des [pseudo]-registres
  *
- * Copyright (C) 2012 Cyrille Bagard
+ * Copyright (C) 2012-2013 Cyrille Bagard
  *
  *  This file is part of OpenIDA.
  *
@@ -24,30 +24,399 @@
 #include "reduce.h"
 
 
-#if 0
+#include <malloc.h>
 
 
+#include "../../decomp/expr/assign.h"
+#include "../../decomp/expr/block.h"
+#include "../../decomp/expr/immediate.h"
+#include "../../decomp/expr/pseudo.h"
 
-/* Mémorisation de l'usage de chaque variable */
-typedef struct _var_usage
+
+
+/* ------------------------ DECOMPTE DES USAGES DE VARIABLES ------------------------ */
+
+
+/* Mémorisation de l'usage d'une variable */
+typedef struct _assigned_value
+{
+    GDecInstruction *value;                 /* Valeur de cette variable    */
+
+    GDecInstruction *assign;                /* Lieu d'assignation          */
+    GDecInstruction *parent;                /* Zone à nettoyer au besoin   */
+
+    size_t used_counter;                    /* Décompte des utilisations   */
+    size_t shared_counter;                  /* Partage entre tables        */
+
+} assigned_value;
+
+
+/* Conserve tous les éléments concernant une assignation. */
+static assigned_value *memorize_assigned_value(GDecInstruction *, GDecInstruction *, GDecInstruction *);
+
+/* Met (éventuellement) fin à un suivi d'assignation. */
+static void forget_assigned_value(assigned_value *);
+
+/* Constitue un lieu de conservation d'associations pour bloc. */
+static GHashTable *create_tracking_table(GHashTable *);
+
+/* Met à jour les décomptes des différentes assignations. */
+static void merge_usages(GHashTable *, GHashTable *);
+
+/* Prend notre d'une assignation d'une valeur à une variable. */
+static void note_new_variable(GHashTable *, GDecInstruction *, assigned_value *);
+
+
+
+/* ---------------------- VISITES DES INSTRUCTIONS DECOMPILEES ---------------------- */
+
+
+/* Prend note de tous les accès aux différentes variables. */
+static void collect_used_variables(GDecInstruction *, GDecInstruction *, GHashTable *);
+
+/* Procède au remplacement de variables à rejeter. */
+static void replace_useless_variable(GDecInstruction *, GHashTable *);
+
+/* Visite un groupe d'instructions décompilées. */
+static bool visit_instructions_block(GDecInstruction *, GDecInstruction *, DecInstrVisitFlags, GHashTable **);
+
+
+
+/* ---------------------------------------------------------------------------------- */
+/*                          DECOMPTE DES USAGES DE VARIABLES                          */
+/* ---------------------------------------------------------------------------------- */
+
+
+/******************************************************************************
+*                                                                             *
+*  Paramètres  : value  = nouvelle valeur assignée à suivre.                  *
+*                assign = instruction où la valeur est assignée.              *
+*                parent = bloc d'instructions à soulager en cas d'effacement. *
+*                table  = mémorisation des usages de variables.               *
+*                                                                             *
+*  Description : Conserve tous les éléments concernant une assignation.       *
+*                                                                             *
+*  Retour      : Structure mise en place.                                     *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+static assigned_value *memorize_assigned_value(GDecInstruction *value, GDecInstruction *assign, GDecInstruction *parent)
+{
+    assigned_value *result;                 /* Mémorisation à retourner    */
+
+    result = (assigned_value *)calloc(1, sizeof(assigned_value));
+
+    g_object_ref(G_OBJECT(value));
+    result->value = value;
+
+    g_object_ref(G_OBJECT(assign));
+    g_object_ref(G_OBJECT(parent));
+    result->assign = assign;
+    result->parent = parent;
+
+    result->used_counter = 0;
+    result->shared_counter = 0;
+
+    return result;
+
+}
+
+
+/******************************************************************************
+*                                                                             *
+*  Paramètres  : val = structure à libérer de la mémoire.                     *
+*                                                                             *
+*  Description : Met (éventuellement) fin à un suivi d'assignation.           *
+*                                                                             *
+*  Retour      : -                                                            *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+static void forget_assigned_value(assigned_value *val)
+{
+    if (--val->shared_counter == 0)
+    {
+        g_object_unref(G_OBJECT(val->value));
+
+        g_object_unref(G_OBJECT(val->assign));
+        g_object_unref(G_OBJECT(val->parent));
+
+        free(val);
+
+    }
+
+}
+
+
+/******************************************************************************
+*                                                                             *
+*  Paramètres  : parent = éventuel bloc d'instructions parent ou NULL.        *
+*                                                                             *
+*  Description : Constitue un lieu de conservation d'associations pour bloc.  *
+*                                                                             *
+*  Retour      : Table prête à emploi.                                        *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+static GHashTable *create_tracking_table(GHashTable *parent)
+{
+    GHashTable *result;                     /* Création à retourner        */
+    GHashTableIter iter;                    /* Boucle de parcours          */
+    GDecInstruction *var;                   /* Variable assignée           */
+    assigned_value *val;                    /* Valeur assignée             */
+
+    result = g_hash_table_new_full(NULL, NULL, g_object_unref,
+                                   (GDestroyNotify)forget_assigned_value);
+
+    if (parent != NULL)
+    {
+        g_hash_table_iter_init(&iter, parent);
+
+        while (g_hash_table_iter_next(&iter, (gpointer *)&var, (gpointer *)&val))
+            note_new_variable(result, var, val);
+
+    }
+
+    return result;
+
+}
+
+
+/******************************************************************************
+*                                                                             *
+*  Paramètres  : table = conservation des associations variable <-> valeur.   *
+*                sub   = conservation issue d'un sous bloc.                   *
+*                                                                             *
+*  Description : Met à jour les décomptes des différentes assignations.       *
+*                                                                             *
+*  Retour      : -                                                            *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+static void merge_usages(GHashTable *table, GHashTable *sub)
+{
+    GHashTableIter iter;                    /* Boucle de parcours          */
+    GDecInstruction *var;                   /* Variable assignée           */
+    assigned_value *val;                    /* Valeur assignée             */
+    assigned_value *update;                 /* Même valeur, mise à jour    */
+
+    g_hash_table_iter_init(&iter, table);
+
+    while (g_hash_table_iter_next(&iter, (gpointer *)&var, (gpointer *)&val))
+    {
+        update = (assigned_value *)g_hash_table_lookup(sub, var);
+
+        val->used_counter = update->used_counter;
+
+        g_hash_table_remove(sub, var);
+
+    }
+
+}
+
+
+/******************************************************************************
+*                                                                             *
+*  Paramètres  : table = conservation des associations variable <-> valeur.   *
+*                var   = variable en place à suivre.                          *
+*                val   = valeur associée.                                     *
+*                                                                             *
+*  Description : Prend notre d'une assignation d'une valeur à une variable.   *
+*                                                                             *
+*  Retour      : -                                                            *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+static void note_new_variable(GHashTable *table, GDecInstruction *var, assigned_value *val)
+{
+    g_object_ref(G_OBJECT(var));
+    val->shared_counter++;
+
+    g_hash_table_insert(table, var, val);
+
+}
+
+
+
+/* ---------------------------------------------------------------------------------- */
+/*                        VISITES DES INSTRUCTIONS DECOMPILEES                        */
+/* ---------------------------------------------------------------------------------- */
+
+
+/******************************************************************************
+*                                                                             *
+*  Paramètres  : instr  = instruction visitée.                                *
+*                parent = instruction parente.                                *
+*                table  = mémorisation des usages de variables.               *
+*                                                                             *
+*  Description : Prend note de tous les accès aux différentes variables.      *
+*                                                                             *
+*  Retour      : -                                                            *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+static void collect_used_variables(GDecInstruction *instr, GDecInstruction *parent, GHashTable *table)
+{
+    GAssignExpression *assign;              /* Instruction d'assignation   */
+    GDecInstruction *dest;                  /* Variable de destination     */
+    bool valid;                             /* Destination valide ?        */
+    GDecInstruction *src;                   /* Valeur de source            */
+    assigned_value *value;                  /* Valeur et ses informations  */
+
+    if (G_IS_ASSIGN_EXPRESSION(instr))
+    {
+        assign = G_ASSIGN_EXPRESSION(instr);
+
+        dest = G_DEC_INSTRUCTION(g_assign_expression_get_dest(assign));
+
+        if (G_IS_PSEUDO_REGISTER(dest))
+            valid = (g_pseudo_register_get_usage(G_PSEUDO_REGISTER(dest)) == PRU_LOCAL);
+        else
+            valid = true;
+
+        if (valid)
+        {
+            src = G_DEC_INSTRUCTION(g_assign_expression_get_src(assign));
+
+            value = memorize_assigned_value(src, instr, parent);
+            note_new_variable(table, dest, value);
+
+        }
+
+    }
+    else
+    {
+        value = (assigned_value *)g_hash_table_lookup(table, instr);
+
+        if (value != NULL)
+            value->used_counter++;
+
+    }
+
+}
+
+
+/******************************************************************************
+*                                                                             *
+*  Paramètres  : block = bloc d'instructions décompilées à traiter.           *
+*                table = mémorisation des usages de variables.                *
+*                                                                             *
+*  Description : Procède au remplacement de variables à rejeter.              *
+*                                                                             *
+*  Retour      : -                                                            *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+static void replace_useless_variable(GDecInstruction *block, GHashTable *table)
 {
-    GDecInstruction *var;                   /* Variable manipulée          */
+    GHashTableIter iter;                    /* Boucle de parcours          */
+    GDecInstruction *var;                   /* Variable assignée           */
+    assigned_value *val;                    /* Valeur assignée             */
+    bool replace;                           /* Ordre de remplacement       */
+
+    g_hash_table_iter_init(&iter, table);
+
+    while (g_hash_table_iter_next(&iter, (gpointer *)&var, (gpointer *)&val))
+    {
+        replace = G_IS_IMM_EXPRESSION(val->value);
+        replace |= (val->used_counter == 2);    /* 1 assign. + 1 usage */
+
+        if (!replace) continue;
 
-    size_t ref_counter;                     /* Décompte des utilisations   */
-    GDecInstruction *creation;              /* Emplacement de la création  */
-    GDecInstruction *usage;                 /* Lieu de dernère utilisation */
+        g_expr_block_delete_item(G_EXPR_BLOCK(val->parent), val->assign);
 
-} var_usage;
+        g_dec_instruction_replace(block, var, val->value);
 
-/* Réduction des usages */
-typedef struct _usage_reduc
+    }
+
+}
+
+
+/******************************************************************************
+*                                                                             *
+*  Paramètres  : instr  = instruction visitée.                                *
+*                parent = instruction parente.                                *
+*                flags  = moments des appels réalisés en retour.              *
+*                table  = mémorisation des usages de variables.               *
+*                                                                             *
+*  Description : Visite un groupe d'instructions décompilées.                 *
+*                                                                             *
+*  Retour      : true afin d'aller jusqu'au terme du parcours.                *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+static bool visit_instructions_block(GDecInstruction *instr, GDecInstruction *parent, DecInstrVisitFlags flags, GHashTable **table)
 {
+    GHashTable *sub;                        /* Associations pour sous-bloc */
+
+    if (G_IS_EXPR_BLOCK(instr))
+    {
+        /* Entrée dans un bloc : on crée un contexte propre au bloc ! */
+        if (flags == DVF_ENTER)
+        {
+            g_object_set_data(G_OBJECT(instr), "var_collect", *table);
+            *table = create_tracking_table(*table);
+        }
+
+        /* Sortie du bloc : actions locales + purge ! */
+        else if (flags == DVF_EXIT)
+        {
+            sub = *table;
+            *table = (GHashTable *)g_object_get_data(G_OBJECT(instr), "var_collect");
+
+            if (*table != NULL)
+                merge_usages(*table, sub);
 
+            replace_useless_variable(instr, sub);
+            g_hash_table_unref(sub);
 
+        }
 
-} usage_reduc;
+    }
 
+    else if (flags == DVF_ENTER)
+        collect_used_variables(instr, parent, *table);
+
+    return true;
+
+}
+
+
+/******************************************************************************
+*                                                                             *
+*  Paramètres  : instr = instructions à traiter.                              *
+*                                                                             *
+*  Description : Réduit le nombre de variables utilisées, via propagations.   *
+*                                                                             *
+*  Retour      : -                                                            *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+void reduce_used_variables(GDecInstruction *instr)
+{
+    GHashTable *table;
 
-#endif
+    table = NULL;
 
+    g_dec_instruction_visit(instr, (dec_instr_visitor_cb)visit_instructions_block,
+                            DVF_ENTER | DVF_EXIT, &table);
 
+}