diff options
author | Cyrille Bagard <nocbos@gmail.com> | 2016-03-26 19:56:04 (GMT) |
---|---|---|
committer | Cyrille Bagard <nocbos@gmail.com> | 2016-03-26 19:56:04 (GMT) |
commit | 9895df71ae6ea14e09478cc243227b7b3a2139a3 (patch) | |
tree | 071cd1ad6d92211e100f179bca0ea29e6ac62959 /src/analysis/disass/loop.c | |
parent | d07168a24ab39cad0e3cb69ed8c5e46c7a2dcdf3 (diff) |
Extracted the logic of code nodes for better processing.
Diffstat (limited to 'src/analysis/disass/loop.c')
-rw-r--r-- | src/analysis/disass/loop.c | 366 |
1 files changed, 34 insertions, 332 deletions
diff --git a/src/analysis/disass/loop.c b/src/analysis/disass/loop.c index 94916f7..dd0b661 100644 --- a/src/analysis/disass/loop.c +++ b/src/analysis/disass/loop.c @@ -28,39 +28,14 @@ #include <malloc.h> -#include "../../common/bits.h" - - - -/* Description de noeud, en référence à "Compilers: Principles, Techniques, and Tools" */ -typedef struct _dragon_node -{ - GArchInstruction *first; /* Arrivée d'un lien (début) */ - GArchInstruction *last; /* Départ d'un lien (fin) */ - - bitfield_t *bits; /* Représentation par masque */ - -} dragon_node; +#include "dragon.h" -/* Définition des blocs d'allocation */ -#define NODE_ALLOC_SIZE 100 -/* Dénombre le nombre de noeuds présents dans une routine. */ -static dragon_node *create_dragon_nodes(const GArchProcessor *, const instr_coverage *, const mrange_t *, const vmpa2t *, size_t *); -/* Termine l'initialisation de noeuds trouvés dans une routine. */ -static void define_mask_for_nodes(dragon_node *, size_t); -/* Supprime de la mémoire tous les noeuds détectés. */ -static void delete_dragon_nodes(dragon_node *, size_t); -/* Recherche un noeud selon son intruction de départ. */ -static dragon_node *find_node_for_instruction(dragon_node *, size_t, bool, const GArchInstruction *); - -/* Détermine toute la chaîne hiérarchique de domination. */ -static void compute_all_dominators(dragon_node *, size_t); /* Matérialise les liens de retour arrière en tant que boucles. */ static void detect_back_edges(dragon_node *, size_t); @@ -70,294 +45,6 @@ static void track_loops_in_code(const GArchProcessor *, const instr_coverage *, -/****************************************************************************** -* * -* Paramètres : proc = ensemble d'instructions à parcourir. * -* coverage = zone de couverture où rechercher des instructions.* -* range = zone de couverture de la routine analysée. * -* start = adresse du début de l'analyse. * -* count = taille de la liste de noeuds retournés. [OUT] * -* * -* Description : Dénombre le nombre de noeuds présents dans une routine. * -* * -* Retour : Liste de noeuds initialisés de façon incomplète. * -* * -* Remarques : - * -* * -******************************************************************************/ - -static dragon_node *create_dragon_nodes(const GArchProcessor *proc, const instr_coverage *coverage, const mrange_t *range, const vmpa2t *start, size_t *count) -{ - dragon_node *result; /* Liste à créer et renvoyer */ - size_t allocated; /* Dimensionnement en mémoire */ - GArchInstruction *last; /* Mémorisation du passé */ - GArchInstruction *iter; /* Boucle de parcours */ - const mrange_t *irange; /* Emplacement d'instruction */ - InstructionLinkType *types; /* Type de lien entre instr. */ - size_t scount; /* Nombre de liens de dest. */ - size_t i; /* Boucle de parcours */ - dragon_node *new; /* Nouvel élément à créer */ - - result = NULL; - *count = 0; - - allocated = 0; - - for (last = NULL, iter = g_arch_processor_find_covered_instr_by_address(proc, coverage, start); - iter != NULL; - last = iter, iter = g_arch_instruction_get_next_iter(iter /* FIXME : list*/, iter, ~0)) - { - /* L'instruction sort-elle des clous ? */ - - irange = g_arch_instruction_get_range(iter); - - if (!mrange_contains_mrange(range, irange)) - break; - - /* Analyse des sources */ - - if (result == NULL) - { - (*count)++; - - if (*count >= allocated) - { - allocated += NODE_ALLOC_SIZE; - result = (dragon_node *)realloc(result, allocated * sizeof(dragon_node)); - } - - new = &result[*count - 1]; - - new->first = iter; - - } - else - { - scount = g_arch_instruction_get_sources(iter, NULL, &types); - if (scount == 0) continue; - - for (i = 0; i < scount; 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: - - if (*count > 0) - result[*count - 1].last = last; - - (*count)++; - i = scount; - - if (*count >= allocated) - { - allocated += NODE_ALLOC_SIZE; - result = (dragon_node *)realloc(result, allocated * sizeof(dragon_node)); - } - - new = &result[*count - 1]; - - new->first = iter; - - break; - - default: - break; - - } - - } - - } - - if (*count > 0) - result[*count - 1].last = last; - - return result; - -} - - -/****************************************************************************** -* * -* Paramètres : nodes = liste de noeuds détectés dans une routine. * -* count = taille de cette liste de noeuds à traiter. * -* * -* Description : Termine l'initialisation de noeuds trouvés dans une routine. * -* * -* Retour : - * -* * -* Remarques : - * -* * -******************************************************************************/ - -static void define_mask_for_nodes(dragon_node *nodes, size_t count) -{ - size_t i; /* Boucle de parcours */ - - for (i = 0; i < count; i++) - nodes[i].bits = create_bit_field(count, i > 0); - - set_in_bit_field(nodes[0].bits, 0, 1); - -} - - -/****************************************************************************** -* * -* Paramètres : nodes = liste de noeuds détectés dans une routine. * -* count = taille de cette liste de noeuds à traiter. * -* * -* Description : Supprime de la mémoire tous les noeuds détectés. * -* * -* Retour : - * -* * -* Remarques : - * -* * -******************************************************************************/ - -static void delete_dragon_nodes(dragon_node *nodes, size_t count) -{ - size_t i; /* Boucle de parcours */ - - for (i = 0; i < count; i++) - delete_bit_field(nodes[i].bits); - - free(nodes); - -} - - -/****************************************************************************** -* * -* Paramètres : nodes = liste de noeuds détectés dans une routine. * -* count = taille de cette liste de noeuds à parcourir. * -* final = précise si l'instruction visée est la première. * -* instr = instruction à retrouver en tant que début de noeud. * -* * -* Description : Recherche un noeud selon son intruction de départ. * -* * -* Retour : Noeud trouvé ou NULL si aucune trouvaille. * -* * -* Remarques : - * -* * -******************************************************************************/ - -static dragon_node *find_node_for_instruction(dragon_node *nodes, size_t count, bool final, const GArchInstruction *instr) -{ - dragon_node *result; /* Résultat des recherches */ - const mrange_t *irange; /* Emplacement d'instruction */ - - int find_node_from_range(const mrange_t *range, const dragon_node *node) - { - int status; /* Bilan à retourner */ - const mrange_t *nrange; /* Emplacement de noeud */ - - nrange = g_arch_instruction_get_range(final ? node->last : node->first); - - status = cmp_mrange(range, nrange); - - return status; - - } - - irange = g_arch_instruction_get_range(instr); - - result = bsearch(irange, nodes, count, sizeof(dragon_node), (__compar_fn_t)find_node_from_range); - - return result; - -} - - -/****************************************************************************** -* * -* Paramètres : nodes = liste de noeuds détectés dans une routine. * -* count = taille de cette liste de noeuds à traiter. * -* * -* Description : Détermine toute la chaîne hiérarchique de domination. * -* * -* Retour : - * -* * -* Remarques : - * -* * -******************************************************************************/ - -static void compute_all_dominators(dragon_node *nodes, size_t count) -{ - bitfield_t *inter; /* Intersection de dominations */ - bool changed; /* Note un changement qq part */ - size_t k; /* Boucle de parcours #1 */ - dragon_node *node; /* Noeud à traiter */ - dragon_node *predecessor; /* Noeud prédécesseur direct */ - GArchInstruction **srcs; /* Instructions d'origine */ - InstructionLinkType *types; /* Type de lien entre instr. */ - size_t scount; /* Nombre de liens de source */ - size_t i; /* Boucle de parcours #2 */ - - inter = create_bit_field(count, false); - - do - { - changed = false; - - for (k = 1; k < count; k++) - { - node = &nodes[k]; - - set_all_in_bit_field(inter); - - scount = g_arch_instruction_get_sources(node->first, &srcs, &types); - assert(scount > 0); - - for (i = 0; i < scount; 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: - - predecessor = find_node_for_instruction(nodes, count, true, srcs[i]); - - - printf(" -- finding pred @ 0x%08x -> 0x%08x :: %p\n", - (unsigned int)g_arch_instruction_get_range(node->first)->addr.virtual, - (unsigned int)g_arch_instruction_get_range(srcs[i])->addr.virtual, - predecessor); - - - - if (predecessor == NULL) break; - - and_bit_field(inter, predecessor->bits); - break; - - default: - break; - - } - - set_in_bit_field(inter, k, 1); - - if (!is_bit_field_equal_to(node->bits, inter)) - { - copy_bit_field(node->bits, inter); - changed = true; - } - - } - - } - while (changed); - - delete_bit_field(inter); - -} - /****************************************************************************** @@ -377,6 +64,8 @@ static void detect_back_edges(dragon_node *nodes, size_t count) { size_t k; /* Boucle de parcours #1 */ dragon_node *node; /* Noeud à traiter */ + const bitfield_t *dominators; /* Liste de dominateurs */ + GArchInstruction *last; /* Instruction finale de noeud */ GArchInstruction **dests; /* Instr. visée par une autre */ InstructionLinkType *types; /* Type de lien entre lignes */ size_t dcount; /* Nombre de liens de dest. */ @@ -390,24 +79,33 @@ static void detect_back_edges(dragon_node *nodes, size_t count) for (k = 0; k < count; k++) { - node = &nodes[k]; + GArchInstruction *first; + + node = get_dragon_node(nodes, k); + + dominators = get_domination_bits(node); + + get_dragon_node_bounding_instructions(node, &first, &last); + printf("#[ node %zu ]# @ 0x%08x / 0x%08x - mask = 0x%08lx\n", k, - (unsigned int)g_arch_instruction_get_range(node->first)->addr.virtual, - (unsigned int)g_arch_instruction_get_range(node->last)->addr.virtual, - gfw(node->bits)); + (unsigned int)g_arch_instruction_get_range(first)->addr.virtual, + (unsigned int)g_arch_instruction_get_range(last)->addr.virtual, + gfw(dominators)); } printf("\n"); - - for (k = 1; k < count; k++) { - node = &nodes[k]; + node = get_dragon_node(nodes, k); + + dominators = get_domination_bits(node); - dcount = g_arch_instruction_get_destinations(node->last, &dests, &types, NULL); + get_dragon_node_bounding_instructions(node, NULL, &last); + + dcount = g_arch_instruction_get_destinations(last, &dests, &types, NULL); if (dcount == 0) continue; for (i = 0; i < dcount; i++) @@ -422,17 +120,17 @@ static void detect_back_edges(dragon_node *nodes, size_t count) target = find_node_for_instruction(nodes, count, false, dests[i]); if (target == NULL) break; - id = (target - nodes); + id = get_dragon_node_index(nodes, target); - if (test_in_bit_field(node->bits, id, 1)) + if (test_in_bit_field(dominators, id, 1)) { printf("BACKEDGE :: 0x%08lx -> 0x%08lx\n", - (unsigned int)g_arch_instruction_get_range(node->last)->addr.virtual, + (unsigned int)g_arch_instruction_get_range(last)->addr.virtual, (unsigned int)g_arch_instruction_get_range(dests[i])->addr.virtual); - /* status = */g_arch_instruction_change_link(node->last, dests[i], types[i], ILT_LOOP); + /* status = */g_arch_instruction_change_link(last, dests[i], types[i], ILT_LOOP); } @@ -468,25 +166,29 @@ static void detect_back_edges(dragon_node *nodes, size_t count) static void track_loops_in_code(const GArchProcessor *proc, const instr_coverage *coverage, const mrange_t *range, const vmpa2t *start, memfield_t *flow) { + dragon_knight *knight; /* Complexité de code posée */ dragon_node *nodes; /* Liste des noeuds détectés */ size_t count; /* Taille de cette liste */ - nodes = create_dragon_nodes(proc, coverage, range, start, &count); + knight = begin_dragon_knight(proc, coverage, range, start); + if (knight == NULL) return; - if (nodes == NULL) return; + assert(knight != NULL); - assert(nodes != NULL); - printf("nodes count :: %d\n", (int)count); - define_mask_for_nodes(nodes, count); + get_dragon_knight_content(knight, &nodes, &count); + + + printf("nodes count :: %d\n", (int)count); compute_all_dominators(nodes, count); detect_back_edges(nodes, count); - delete_dragon_nodes(nodes, count); + + end_dragon_knight(knight); } |