diff options
author | Cyrille Bagard <nocbos@gmail.com> | 2016-10-09 11:35:00 (GMT) |
---|---|---|
committer | Cyrille Bagard <nocbos@gmail.com> | 2016-10-09 11:35:00 (GMT) |
commit | 3628caa2311ee89ad0d2a0aa2438d7e85b497da4 (patch) | |
tree | bf81ed850cec1a35cdcaeff25a3479182e365c3c /src/gtkext/graph/nodes/flow.c | |
parent | b6427496bde6f3ab34dc62d6b437c4f8a3a29b2d (diff) |
Defined a new and simpler way to produce graphical view of basic blocks.
Diffstat (limited to 'src/gtkext/graph/nodes/flow.c')
-rw-r--r-- | src/gtkext/graph/nodes/flow.c | 1329 |
1 files changed, 0 insertions, 1329 deletions
diff --git a/src/gtkext/graph/nodes/flow.c b/src/gtkext/graph/nodes/flow.c deleted file mode 100644 index e19cacb..0000000 --- a/src/gtkext/graph/nodes/flow.c +++ /dev/null @@ -1,1329 +0,0 @@ - -/* 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 <http://www.gnu.org/licenses/>. - */ - - -#include "flow.h" - - -#include <assert.h> -#include <malloc.h> -#include <stdlib.h> - - -#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; - -} |