/* Chrysalide - Outil d'analyse de fichiers binaires
* flow.c - encapsulation graphique des blocs d'exécution
*
* Copyright (C) 2013 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 .
*/
#include "flow.h"
#include
#include
#include
#include "../layout.h"
#include "../node-int.h"
/* Type d'un accrochage pour lien */
struct _node_slot_t
{
GArchInstruction *instr; /* Instruction liée */
size_t group_index; /* Rang dans le grp d'origine */
InstructionLinkType type; /* Type de lien à représenter */
size_t slot_index; /* Position dans l'accroche */
gint x; /* Abscisse graphique du rendu */
};
/* Encapsulation graphique d'un bloc d'exécution (instance) */
struct _GFlowNode
{
GGraphNode parent; /* A laisser en premier */
GFlowBlock *block; /* Bloc d'exécution associé */
GtkBufferView *view; /* Représentation graphique */
node_slot_t *entries; /* Positions des pts d'entrées */
size_t entries_count; /* Nombre de ces points */
node_slot_t *exits; /* Positions des pts de sorties*/
size_t exits_count; /* Nombre de ces points */
};
/* Encapsulation graphique d'un bloc d'exécution (classe) */
struct _GFlowNodeClass
{
GGraphNodeClass parent; /* A laisser en premier */
};
#define SPACE_BETWEEN_SLOT 15
/* Initialise la classe des encapsulations de bloc d'exécution. */
static void g_flow_node_class_init(GFlowNodeClass *);
/* Initialise une encapsulation de bloc d'exécution. */
static void g_flow_node_init(GFlowNode *);
/* Supprime toutes les références externes. */
static void g_flow_node_dispose(GFlowNode *);
/* Procède à la libération totale de la mémoire. */
static void g_flow_node_finalize(GFlowNode *);
/* Fournit le rang du noeud dans le graphique. */
static unsigned int g_flow_node_get_rank(const GFlowNode *);
/* Organise le contenu du noeud selon l'axe des abscisses. */
static void g_flow_node_prepare_x_line(GFlowNode *, GGraphNode *);
/* Parcourt tous les blocs d'instructions dans un ordre donné. */
static bool g_flow_node_visit_flow_nodes(GFlowNode *, graph_node_visitor_cb, void *);
/* ------------------------ GESTION DES ACCROCHES D'UN NOEUD ------------------------ */
/* Prépare les points d'entrées du noeud. */
static void g_flow_node_setup_entry_slots(GFlowNode *);
/* Prépare les points de sorties du noeud. */
static void g_flow_node_setup_exit_slots(GFlowNode *);
/* Etablit un lien entre deux noeuds graphiques. */
static node_slot_t *g_flow_node_get_slot(const GFlowNode *, bool, GArchInstruction *, size_t);
/* Localise un point d'accroche à un noeud graphique. */
static gint g_flow_node_get_slot_offset(const GFlowNode *, bool, const node_slot_t *);
/* Indique le type définit par la GLib pour l'encapsulation d'un bloc d'exécution. */
G_DEFINE_TYPE(GFlowNode, g_flow_node, G_TYPE_GRAPH_NODE);
/******************************************************************************
* *
* Paramètres : klass = classe à initialiser. *
* *
* Description : Initialise la classe des encapsulations de bloc d'exécution. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void g_flow_node_class_init(GFlowNodeClass *klass)
{
GObjectClass *object; /* Autre version de la classe */
GGraphNodeClass *node_class; /* Version parente de la classe*/
object = G_OBJECT_CLASS(klass);
node_class = G_GRAPH_NODE_CLASS(klass);
object->dispose = (GObjectFinalizeFunc/* ! */)g_flow_node_dispose;
object->finalize = (GObjectFinalizeFunc)g_flow_node_finalize;
node_class->get_rank = (get_node_rank_fc)g_flow_node_get_rank;
node_class->prepare_x = (node_prepare_x_fc)g_flow_node_prepare_x_line;
node_class->visit = (visit_flow_nodes_fc)g_flow_node_visit_flow_nodes;
}
/******************************************************************************
* *
* Paramètres : node = instance à initialiser. *
* *
* Description : Initialise une encapsulation de bloc d'exécution. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void g_flow_node_init(GFlowNode *node)
{
}
/******************************************************************************
* *
* Paramètres : node = instance d'objet GLib à traiter. *
* *
* Description : Supprime toutes les références externes. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void g_flow_node_dispose(GFlowNode *node)
{
size_t i; /* Boucle de parcours */
g_object_unref(G_OBJECT(node->block));
g_object_unref(G_OBJECT(node->view));
for (i = 0; i < node->entries_count; i++)
g_object_unref(G_OBJECT(node->entries[i].instr));
for (i = 0; i < node->exits_count; i++)
g_object_unref(G_OBJECT(node->exits[i].instr));
G_OBJECT_CLASS(g_flow_node_parent_class)->dispose(G_OBJECT(node));
}
/******************************************************************************
* *
* Paramètres : node = instance d'objet GLib à traiter. *
* *
* Description : Procède à la libération totale de la mémoire. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void g_flow_node_finalize(GFlowNode *node)
{
if (node->entries != NULL)
free(node->entries);
if (node->exits != NULL)
free(node->exits);
G_OBJECT_CLASS(g_flow_node_parent_class)->finalize(G_OBJECT(node));
}
/******************************************************************************
* *
* Paramètres : block = bloc d'exécution représenté graphiquement. *
* view = morceau d'affichage à représenter. *
* *
* Description : Encapsule graphiquement un bloc d'exécution. *
* *
* Retour : Adresse de la structure mise en place. *
* *
* Remarques : - *
* *
******************************************************************************/
GGraphNode *g_flow_node_new(GFlowBlock *block, GtkBufferView *view)
{
GFlowNode *result; /* Structure à retourner */
GtkRequisition requisition; /* Taille à l'écran actuelle */
result = g_object_new(G_TYPE_FLOW_NODE, NULL);
g_object_ref(G_OBJECT(block));
g_object_ref(G_OBJECT(view));
result->block = block;
result->view = view;
gtk_widget_show(GTK_WIDGET(result->view));
gtk_widget_size_allocate(GTK_WIDGET(result->view), (GtkAllocation []) { { 0, 0, 100, 100 } });
gtk_widget_get_preferred_size(GTK_WIDGET(result->view), NULL, &requisition);
G_GRAPH_NODE(result)->alloc.width = requisition.width;
G_GRAPH_NODE(result)->alloc.height = requisition.height;
g_flow_node_setup_entry_slots(result);
g_flow_node_setup_exit_slots(result);
return G_GRAPH_NODE(result);
}
/******************************************************************************
* *
* Paramètres : node = noeud graphique à consulter. *
* *
* Description : Fournit le rang du noeud dans le graphique. *
* *
* Retour : Indice supérieur ou égal à zéro. *
* *
* Remarques : - *
* *
******************************************************************************/
static unsigned int g_flow_node_get_rank(const GFlowNode *node)
{
return g_flow_block_get_rank(node->block);
}
/******************************************************************************
* *
* Paramètres : node = noeud d'encapsulation à traiter. *
* nodes = ensemble des noeuds en place. *
* *
* Description : Organise le contenu du noeud selon l'axe des abscisses. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void g_flow_node_prepare_x_line(GFlowNode *node, GGraphNode *nodes)
{
GGraphNode *base; /* Autre vision de l'instance */
GArchInstruction *last; /* Dernière instr. du noeud */
size_t loop_index; /* Indice de sortie en boucle */
GFlowNode *target; /* Bloc visé par le lien */
node_slot_t *dest_slot; /* Accrochage d'arrivée */
pending_position pos; /* Position à transmettre */
GFlowNode *target_a; /* Bloc visé par le lien #a */
GFlowNode *target_b; /* Bloc visé par le lien #b */
unsigned int rank_a; /* Indice du rang associé #a */
unsigned int rank_b; /* Indice du rang associé #b */
GGraphNode *container; /* Conteneur à positionner */
base = G_GRAPH_NODE(node);
g_flow_block_get_boundary(node->block, NULL, &last);
for (loop_index = 0; loop_index < node->exits_count; loop_index++)
if (node->exits[loop_index].type == ILT_LOOP)
break;
switch (node->exits_count - (loop_index == node->exits_count ? 0 : 1))
{
case 0:
break;
case 1:
if (loop_index == node->exits_count)
{
target = G_FLOW_NODE(find_node_for_first_instruction(nodes, node->exits[0].instr));
/* Cf. commentaire de g_flow_node_link() */
if (target == NULL) break;
dest_slot = g_flow_node_get_slot(target, true,
last, node->exits[0].group_index);
}
else
{
target = G_FLOW_NODE(find_node_for_first_instruction(nodes, node->exits[1].instr));
/* Cf. commentaire de g_flow_node_link() */
if (target == NULL) break;
dest_slot = g_flow_node_get_slot(target, true,
last, node->exits[1].group_index);
}
pos.direct_x = g_flow_node_get_slot_offset(target, true, dest_slot);
pos.direct_x = (G_GRAPH_NODE(target)->alloc.width / 2) - pos.direct_x;
pos.direct_x -= (G_GRAPH_NODE(target)->alloc.width - G_GRAPH_NODE(node)->alloc.width) / 2;
pos.relative_ref = base;
size_t count_and_skip_loop(GFlowNode *n)
{
size_t counter;
for (counter = 0; counter < n->entries_count; counter++)
if (n->entries[counter].type == ILT_LOOP)
break;
return counter < n->entries_count ? n->entries_count - 1 : n->entries_count;
}
if (count_and_skip_loop(target) == 1)
g_graph_node_set_pending_position(G_GRAPH_NODE(target), PPF_DIRECT_X, pos);
break;
case 2:
target_a = G_FLOW_NODE(find_node_for_first_instruction(nodes, node->exits[0].instr));
target_b = G_FLOW_NODE(find_node_for_first_instruction(nodes, node->exits[1].instr));
rank_a = g_flow_node_get_rank(target_a);
rank_b = g_flow_node_get_rank(target_b);
if (rank_a == rank_b)
{
/* On s'assure que le père est centré par rapport aux deux fils */
pos.left_node = G_GRAPH_NODE(target_a);
pos.right_node = G_GRAPH_NODE(target_b);
/**
* Un pré-condition pour pouvoir s'aligner est que les noeuds
* de références soient traités au préalables pour les positions.
* Sinon les assert() coincent dans g_virtual_node_apply_x_line().
*/
if (g_graph_node_find_container_at_same_level(nodes, base, pos.left_node) != NULL
&& g_graph_node_find_container_at_same_level(nodes, base, pos.right_node) != NULL)
{
g_graph_node_set_pending_position(base, PPF_MIDDLE_OF, pos);
}
break;
}
/* Alignement d'un bloc lié */
if (rank_a > rank_b)
{
/* Seuil vertical pour un côté */
container = g_graph_node_find_container_at_same_level(nodes,
G_GRAPH_NODE(node),
G_GRAPH_NODE(target_b));
if (container == NULL) container = G_GRAPH_NODE(target_b);
pos.left_margin = g_flow_node_get_slot_offset(node, false, &node->exits[0]);
pos.relative_ref = base;
g_graph_node_set_pending_position(container, PPF_LEFT_MARGIN, pos);
/* Trait vertical de l'autre côté... */
pos.direct_x = pos.left_margin;
dest_slot = g_flow_node_get_slot(target_a, true,
last, node->exits[0].group_index);
pos.direct_x -= g_flow_node_get_slot_offset(target_a, true, dest_slot);
pos.relative_ref = base;
g_graph_node_set_pending_position(G_GRAPH_NODE(target_a), PPF_DIRECT_X, pos);
}
else
{
/* Seuil vertical pour un côté */
container = g_graph_node_find_container_at_same_level(nodes,
G_GRAPH_NODE(node),
G_GRAPH_NODE(target_a));
if (container == NULL) container = G_GRAPH_NODE(target_a);
pos.right_margin = g_flow_node_get_slot_offset(node, false, &node->exits[1]);
pos.relative_ref = base;
g_graph_node_set_pending_position(container, PPF_RIGHT_MARGIN, pos);
/* Trait vertical de l'autre côté... */
pos.direct_x = pos.right_margin;
dest_slot = g_flow_node_get_slot(target_b, true,
last, node->exits[1].group_index);
pos.direct_x -= g_flow_node_get_slot_offset(target_b, true, dest_slot);
pos.relative_ref = base;
g_graph_node_set_pending_position(G_GRAPH_NODE(target_b), PPF_DIRECT_X, pos);
}
break;
}
}
/******************************************************************************
* *
* Paramètres : node = noeud graphique démarrant la visite. *
* callback = ensemble de blocs à parcourir. *
* data = donnée utilisateur à associer au parcours. *
* *
* Description : Parcourt tous les blocs d'instructions dans un ordre donné. *
* *
* Retour : true si le parcours a été jusqu'à son terme, false sinon. *
* *
* Remarques : - *
* *
******************************************************************************/
static bool g_flow_node_visit_flow_nodes(GFlowNode *node, graph_node_visitor_cb callback, void *data)
{
return callback(G_GRAPH_NODE(node), GVS_NODE, data);
}
/******************************************************************************
* *
* Paramètres : node = noeud graphique à consulter. *
* *
* Description : Fournit le bloc basique à l'origine du bloc graphique. *
* *
* Retour : Bloc brut encapsulé. *
* *
* Remarques : - *
* *
******************************************************************************/
GFlowBlock *g_flow_node_get_block(const GFlowNode *node)
{
return node->block;
}
/******************************************************************************
* *
* Paramètres : node = noeud graphique à consulter. *
* instr = instruction à considérer. *
* *
* Description : Précise si le noeud a pour première instruction celle donnée.*
* *
* Retour : true si la première instruction du noeud est celle indiquée. *
* *
* Remarques : - *
* *
******************************************************************************/
bool g_flow_node_start_with(const GFlowNode *node, GArchInstruction *instr)
{
GArchInstruction *first; /* Première instr. du noeud */
g_flow_block_get_boundary(node->block, &first, NULL);
return (first == instr);
}
/******************************************************************************
* *
* Paramètres : node = noeud graphique à consulter. *
* instr = instruction à considérer. *
* *
* Description : Précise si le noeud a pour dernière instruction celle donnée.*
* *
* Retour : true si la dernière instruction du noeud est celle indiquée. *
* *
* Remarques : - *
* *
******************************************************************************/
bool g_flow_node_end_with(const GFlowNode *node, GArchInstruction *instr)
{
GArchInstruction *last; /* Dernière instr. du noeud */
g_flow_block_get_boundary(node->block, NULL, &last);
return (last == instr);
}
/******************************************************************************
* *
* Paramètres : node = noeud graphique à consulter. *
* ranks = classement à mettre à jour. *
* *
* Description : Précise la hauteur minimale requise pour un noeud. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
void g_flow_node_register_rank(const GFlowNode *node, GGraphRanks *ranks)
{
unsigned int index; /* Indice du rang associé */
index = g_flow_node_get_rank(node);
g_graph_ranks_set_min_height(ranks, index, G_GRAPH_NODE(node)->alloc.height);
}
/******************************************************************************
* *
* Paramètres : node = noeud graphique à mettre à jour. *
* ranks = classement à consulter. *
* *
* Description : Définit l'ordonnée de l'espace attribué à un noeud. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
void g_flow_node_apply_rank(GFlowNode *node, GGraphRanks *ranks)
{
unsigned int index; /* Indice du rang associé */
index = g_flow_node_get_rank(node);
G_GRAPH_NODE(node)->alloc.y = g_graph_ranks_get_y_for_rank(ranks, index);
}
/******************************************************************************
* *
* Paramètres : node = noeud graphique à mettre à jour. *
* layout = disposition globale du graphique. *
* nodes = ensemble des noeuds en place. *
* *
* Description : Etablit les liaison entre un noeud et ses suivants. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
void g_flow_node_link(GFlowNode *node, GGraphLayout *layout, GGraphNode *nodes)
{
GArchInstruction *last; /* Dernière instr. du noeud */
size_t i; /* Boucle de parcours */
GFlowNode *target; /* Bloc visé par le lien */
node_slot_t *dest_slot; /* Accrochage d'arrivée */
EdgeColor color; /* Couleur du lien à créer */
GGraphEdge *edge; /* Lien à mettre en place */
g_flow_block_get_boundary(node->block, NULL, &last);
for (i = 0; i < node->exits_count; i++)
{
target = G_FLOW_NODE(find_node_for_first_instruction(nodes, node->exits[i].instr));
/**
* Il semblerait que l'adresse ciblée puisse ne correspondre à aucun bloc.
* Ce serait le cas pour un saut avec __gmon_start__ sous ARM, à confirmer (TODO).
* Référence. : http://stackoverflow.com/questions/12697081/what-is-gmon-start-symbol
*/
if (target == NULL) continue;
dest_slot = g_flow_node_get_slot(target, true,
last, node->exits[i].group_index);
switch (node->exits[i].type)
{
case ILT_JUMP_IF_TRUE:
color = EGC_GREEN;
break;
case ILT_JUMP_IF_FALSE:
color = EGC_RED;
break;
case ILT_LOOP:
color = EGC_BLUE;
break;
case ILT_CATCH_EXCEPTION:
color = EGC_DASHED_GRAY;
break;
default:
color = EGC_DEFAULT;
break;
}
edge = g_graph_edge_new(node, &node->exits[i], target, dest_slot, color);
g_graph_layout_add_edge(layout, edge);
}
}
/******************************************************************************
* *
* Paramètres : node = intermédiaire à consulter. *
* view = support de destination. *
* *
* Description : Place un noeud sur son support final. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
void g_flow_node_place(const GFlowNode *node, GtkGraphView *view)
{
gtk_graph_view_put(view, GTK_WIDGET(node->view), &G_GRAPH_NODE(node)->alloc);
}
/* ---------------------------------------------------------------------------------- */
/* GESTION DES ACCROCHES D'UN NOEUD */
/* ---------------------------------------------------------------------------------- */
/******************************************************************************
* *
* Paramètres : node = noeud graphique contenant les accrochées indiquées. *
* a = première accroche à considérer. *
* b = seconde accroche à considérer. *
* *
* Description : Compare deux accroches pour liens entre noeuds. *
* *
* Retour : Bilan de la comparaison : -1, 0 ou 1. *
* *
* Remarques : - *
* *
******************************************************************************/
int g_flow_node_compare_slots_for_edges(const GFlowNode *node, const node_slot_t *a, gint src_a, const node_slot_t *b, gint src_b)
{
int result; /* Bilan à retourner */
GGraphNode *base; /* Accès rapides */
gint middle; /* Milieu du noeud traité */
gint diff_a; /* Distance A <-> centre */
gint diff_b; /* Distance B <-> centre */
/**
* On place les extrémités en premier, afin de les traiter en premier.
*/
int cmp_slot_indexes(const node_slot_t *a, const node_slot_t *b)
{
int result;
if (a->slot_index < b->slot_index)
result = 1;
else if (a->slot_index > b->slot_index)
result = -1;
else
result = 0;
return result;
}
switch (node->entries_count)
{
case 0:
case 1:
assert(0);
break;
case 2:
/**
* Le tri se fait simplement : un accroche à gauche, l'autre à droite.
*/
result = cmp_slot_indexes(a, b);
break;
default:
/**
* On donne plus de poids aux accroches éloignées du centre.
* Facile quand les accroches sont distribuées d'un même côté, centre
* à utiliser dans les calculs sinon.
*/
base = G_GRAPH_NODE(node);
middle = base->alloc.x + (base->alloc.width / 2);
/* Les deux accroches sont à gauche */
if (src_a <= middle && src_b <= middle)
result = cmp_slot_indexes(b, a);
/* Les deux accroches sont à droite */
else if (src_a > middle && src_b > middle)
result = cmp_slot_indexes(a, b);
/* Les deux accroches sont de chaque côté */
else
{
diff_a = (middle > src_a ? middle - src_a : src_a - middle);
diff_b = (middle > src_b ? middle - src_b : src_b - middle);
if (diff_a < diff_b)
result = 1;
else if (diff_a > diff_b)
result = -1;
else
result = 0;
}
break;
}
return result;
}
/******************************************************************************
* *
* Paramètres : node = intermédiaire à compléter. *
* *
* Description : Prépare les points d'entrées du noeud. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void g_flow_node_setup_entry_slots(GFlowNode *node)
{
GArchInstruction *first; /* Première instr. du noeud */
GArchInstruction **instrs; /* Instr. visée par une autre */
InstructionLinkType *types; /* Type de lien entre lignes */
size_t icount; /* Nombre de liens de dest. */
size_t usable; /* Nombre de liens utiles ici */
size_t i; /* Boucle de parcours */
size_t used; /* Nombre de liens utilisés */
g_flow_block_get_boundary(node->block, &first, NULL);
g_arch_instruction_rlock_src(first);
icount = g_arch_instruction_get_sources(first, &instrs, &types);
usable = 0;
for (i = 0; i < icount; 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:
case ILT_LOOP:
case ILT_CATCH_EXCEPTION:
usable++;
break;
default:
break;
}
if (usable == 0)
{
node->entries = NULL;
node->entries_count = 0;
}
else
{
node->entries = (node_slot_t *)calloc(usable, sizeof(node_slot_t));
node->entries_count = usable;
}
used = 0;
for (i = 0; i < icount; 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:
case ILT_LOOP:
case ILT_CATCH_EXCEPTION:
g_object_ref(instrs[i]);
node->entries[used].instr = instrs[i];
node->entries[used].type = types[i];
node->entries[used].group_index = g_arch_instruction_compute_group_index(&instrs[i],
instrs, icount);
node->entries[used].slot_index = used;
used++;
break;
default:
break;
}
assert(used == usable);
g_arch_instruction_runlock_src(first);
}
/******************************************************************************
* *
* Paramètres : node = intermédiaire à compléter. *
* *
* Description : Prépare les points de sorties du noeud. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void g_flow_node_setup_exit_slots(GFlowNode *node)
{
GArchInstruction *last; /* Dernière instr. du noeud */
GArchInstruction **instrs; /* Instr. visée par une autre */
InstructionLinkType *types; /* Type de lien entre lignes */
size_t icount; /* Nombre de liens de dest. */
size_t usable; /* Nombre de liens utiles ici */
size_t i; /* Boucle de parcours */
size_t used; /* Nombre de liens utilisés */
g_flow_block_get_boundary(node->block, NULL, &last);
g_arch_instruction_rlock_dest(last);
icount = g_arch_instruction_get_destinations(last, &instrs, &types, NULL);
usable = 0;
for (i = 0; i < icount; 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:
case ILT_LOOP:
case ILT_CATCH_EXCEPTION:
usable++;
break;
default:
break;
}
if (usable == 0)
{
node->exits = NULL;
node->exits_count = 0;
}
else
{
node->exits = (node_slot_t *)calloc(usable, sizeof(node_slot_t));
node->exits_count = usable;
}
used = 0;
for (i = 0; i < icount; 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:
case ILT_LOOP:
case ILT_CATCH_EXCEPTION:
g_object_ref(instrs[i]);
node->exits[used].instr = instrs[i];
node->exits[used].type = types[i];
node->exits[used].group_index = g_arch_instruction_compute_group_index(&instrs[i],
instrs, icount);
node->exits[used].slot_index = used;
used++;
break;
default:
break;
}
assert(used == usable);
g_arch_instruction_runlock_dest(last);
}
/******************************************************************************
* *
* Paramètres : node = noeud graphique à consulter. *
* entry = indique le type d'accrochage recherché. *
* instr = instruction visée. *
* index = indice de groupe pour départager au besoin. *
* *
* Description : Etablit un lien entre deux noeuds graphiques. *
* *
* Retour : Lien graphique mis en place. *
* *
* Remarques : - *
* *
******************************************************************************/
static node_slot_t *g_flow_node_get_slot(const GFlowNode *node, bool entry, GArchInstruction *instr, size_t index)
{
node_slot_t *result; /* Emplacement à retourner */
node_slot_t *list; /* Liste à parcourir */
size_t count; /* Taille de cette liste */
size_t i; /* Boucle de parcours */
if (entry)
{
list = node->entries;
count = node->entries_count;
}
else
{
list = node->exits;
count = node->exits_count;
}
for (i = 0; i < count; i++)
{
result = list + i;
if (result->instr == instr/* && result->group_index == index*/)
break;
}
return (i == count ? NULL : result);
}
/******************************************************************************
* *
* Paramètres : node = noeud graphique à consulter. *
* entry = indique le type d'accrochage recherché. *
* slot = accroche dont l'emplacement est à définir. *
* *
* Description : Localise un point d'accroche à un noeud graphique. *
* *
* Retour : Décallage relatif pour l'accroche fournie. *
* *
* Remarques : - *
* *
******************************************************************************/
static gint g_flow_node_get_slot_offset(const GFlowNode *node, bool entry, const node_slot_t *slot)
{
gint result; /* Valeur à retourner */
node_slot_t *slots; /* Accroches à parcourir */
size_t count; /* Nombre de ces points */
gint slots_width; /* Largeur des accroches */
gint slots_left; /* Abscisse de la première */
size_t index; /* Indice de l'accroche visée */
if (entry)
{
slots = node->entries;
count = node->entries_count;
}
else
{
slots = node->exits;
count = node->exits_count;
}
slots_width = (count - 1) * SPACE_BETWEEN_SLOT;
slots_left = (G_GRAPH_NODE(node)->alloc.width - slots_width) / 2;
index = (slot - slots);
/* BUG_ON(index >= count); */
index = slot->slot_index;
result = slots_left + index * SPACE_BETWEEN_SLOT;
return result;
}
/******************************************************************************
* *
* Paramètres : node = intermédiaire à consulter. *
* nodes = ensemble des noeuds en place. *
* *
* Description : Réorganise au mieux les points d'accroche d'un noeud. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
#include "../../../arch/instruction-int.h"
void g_flow_node_reorder_slots(const GFlowNode *node, GGraphNode *nodes)
{
typedef struct _reordering_params
{
GdkPoint middle; /* Milieu du noeud traité */
bool down_first; /* Liens descendants aux bords */
bool entry; /* Zone d'accrochage aux bouts */
GArchInstruction *instr; /* Instruction du bloc courant */
} reordering_params;
typedef struct _reordered_slot
{
const reordering_params *params; /* Informations partagées */
GdkPoint dest; /* Position à l'extrémité */
size_t orig_index; /* Indice d'accroche d'origine */
} reordered_slot;
GGraphNode *base; /* Accès rapides */
reordering_params params; /* Directives générales */
int cmp_slots_for_reordering(const reordered_slot *a, const reordered_slot *b)
{
const reordering_params *params; /* Informations partagées */
bool on_left_a; /* Lien A vers la gauche ? */
bool on_left_b; /* Lien B vers la gauche ? */
bool go_down_a; /* Lien A vers le bas ? */
bool go_down_b; /* Lien B vers le bas ? */
params = a->params;
/* Première distinction : côté par rapport au centre */
on_left_a = (a->dest.x <= params->middle.x);
on_left_b = (b->dest.x <= params->middle.x);
if (on_left_a && !on_left_b) return -1;
else if (!on_left_a && on_left_b) return 1;
/* On évite les recoupements entre montées et descentes */
go_down_a = (a->dest.y >= params->middle.y);
go_down_b = (b->dest.y >= params->middle.y);
if (go_down_a && !go_down_b) return (params->down_first ? -1 : 1);
else if (!go_down_a && go_down_b) return (params->down_first ? -1 : 1);
/* Au sein d'une même catégorie, on se base uniquement sur la position */
return (a->dest.x <= b->dest.x ? -1 : 1);
}
void reorder_slots(node_slot_t *slots, size_t count, __compar_fn_t cmp, const reordering_params *params, GGraphNode *nodes)
{
reordered_slot *rslots; /* Créneaux réorganisés */
reordered_slot *iter; /* Boucle de parcours #1 */
size_t used; /* Nombre de liens valides */
size_t i; /* Boucle de parcours #2 */
GFlowNode *target; /* Bloc visé par le lien */
node_slot_t *dest_slot; /* Accrochage associé */
rslots = (reordered_slot *)calloc(count, sizeof(reordered_slot));
/* Constitution d'une liste triée */
iter = rslots;
used = 0;
for (i = 0; i < count; i++)
{
iter->params = params;
target = G_FLOW_NODE(_find_node_for_instruction(nodes, slots[i].instr, params->entry));
/* Cf. commentaire de g_flow_node_link() */
if (target == NULL) continue;
dest_slot = g_flow_node_get_slot(target, params->entry,
params->instr, slots[i].group_index);
iter->dest = g_flow_node_get_point_from_slot(target, params->entry, dest_slot);
iter->orig_index = i;
iter++;
used++;
}
/* TODO : utiliser qsort_r, avec params en argument ? */
qsort(rslots, used, sizeof(reordered_slot), cmp);
for (i = 0; i < used; i++)
{
if (rslots[i].orig_index != i)
printf("Could reorder %zu -> %zu\n", rslots[i].orig_index, i);
if (rslots[i].orig_index != i)
slots[rslots[i].orig_index].slot_index = i;
}
free(rslots);
}
base = G_GRAPH_NODE(node);
/* Régorganise les accroches d'entrée */
if (node->entries_count > 1)
{
params.middle.x = base->alloc.x + (base->alloc.width / 2);
params.middle.y = base->alloc.y;
params.down_first = true;
params.entry = false;
g_flow_block_get_boundary(node->block, ¶ms.instr, NULL);
printf(" ### REORDERING ENTRIES OF 0x%08x\n", (unsigned int)params.instr->range.addr.virtual);
reorder_slots(node->entries, node->entries_count, (__compar_fn_t)cmp_slots_for_reordering, ¶ms, nodes);
}
/* Régorganise les accroches de sortie */
if (node->exits_count > 1)
{
params.middle.x = base->alloc.x + (base->alloc.width / 2);
params.middle.y = base->alloc.y + base->alloc.height;
params.down_first = false;
params.entry = true;
g_flow_block_get_boundary(node->block, NULL, ¶ms.instr);
printf(" ### REORDERING EXITS OF 0x%08x\n", (unsigned int)params.instr->range.addr.virtual);
reorder_slots(node->exits, node->exits_count, (__compar_fn_t)cmp_slots_for_reordering, ¶ms, nodes);
}
}
/******************************************************************************
* *
* Paramètres : node = noeud graphique à consulter. *
* entry = indique le type d'accrochage recherché. *
* slot = accroche dont l'emplacement est à définir. *
* *
* Description : Localise un point d'accroche à un noeud graphique. *
* *
* Retour : Emplacement réservé pour l'accroche fournie. *
* *
* Remarques : - *
* *
******************************************************************************/
GdkPoint g_flow_node_get_point_from_slot(const GFlowNode *node, bool entry, const node_slot_t *slot)
{
GGraphNode *base; /* Accès rapides */
GdkPoint result; /* Position à retourner */
node_slot_t *slots; /* Accroches à parcourir */
size_t count; /* Nombre de ces points */
gint slots_width; /* Largeur des accroches */
gint slots_left; /* Abscisse de la première */
size_t index; /* Indice de l'accroche visée */
base = G_GRAPH_NODE(node);
if (entry)
{
result.y = base->alloc.y;
slots = node->entries;
count = node->entries_count;
}
else
{
result.y = base->alloc.y + base->alloc.height;
slots = node->exits;
count = node->exits_count;
}
slots_width = (count - 1) * SPACE_BETWEEN_SLOT;
slots_left = base->alloc.x + (base->alloc.width - slots_width) / 2;
index = (slot - slots)/* / sizeof(node_slot_t)*/;
/* BUG_ON(index >= count); */
if (count > 1 && entry)
printf(" -->> index = %zu vs %zu (max = %zu)\n", index, slot->slot_index, count);
index = slot->slot_index;
result.x = slots_left + index * SPACE_BETWEEN_SLOT;
return result;
}