/* Chrysalide - Outil d'analyse de fichiers binaires
* reduce.c - réduction de l'usage des [pseudo]-registres
*
* Copyright (C) 2012-2017 Cyrille Bagard
*
* This file is part of Chrysalide.
*
* Chrysalide 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.
*
* Chrysalide 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 .
*/
#include "reduce.h"
#include
#include "../../decomp/expr/assign.h"
#include "../../decomp/expr/block.h"
#include "../../decomp/expr/immediate.h"
#include "../../decomp/expr/pseudo.h"
/* ------------------------ 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)
{
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) && (val->used_counter > 1));
replace |= (val->used_counter == 2); /* 1 assign. + 1 usage */
if (!replace) continue;
g_expr_block_delete_item(G_EXPR_BLOCK(val->parent), val->assign);
g_dec_instruction_replace(block, var, val->value);
}
}
/******************************************************************************
* *
* 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);
}
}
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;
table = NULL;
g_dec_instruction_visit(instr, (dec_instr_visitor_cb)visit_instructions_block,
DVF_ENTER | DVF_EXIT, &table);
}