plugin.cpp

#include <gcc-plugin.h>
#include <plugin-version.h>
#include <tree.h>
#include <basic-block.h>
#include <diagnostic.h>
#include <gimple.h>
#include <tree-pass.h>
#include <context.h>
#include <function.h>
#include <gimple-iterator.h>
#include <c-family/c-pragma.h>
#include <vec.h>
#include <bitmap.h>
#include <queue>

// ========== VARIABLES GLOBALES ========== //

int plugin_is_GPL_compatible;

// Mode debug (affichage des informations de débogage)
bool debug_mode = true;

/* Enumération des codes des opérations collectives MPI potentielles à vérifier */
enum mpi_collective_code
{
#define DEFMPICOLLECTIVES(CODE, NAME) CODE,
#include "MPI_collectives.def"
    LAST_AND_UNUSED_MPI_COLLECTIVE_CODE
#undef DEFMPICOLLECTIVES
};

/* Tableau de noms des opérations collectives MPI potentielles à vérifier */
#define DEFMPICOLLECTIVES(CODE, NAME) NAME,
const char *const mpi_collective_name[] = {
#include "MPI_collectives.def"
};
#undef DEFMPICOLLECTIVES

// Vecteur contenant la liste des fonctions à vérifier issue de la directive #pragma ProjetCA mpicoll_check
vec<tree> *fun_vec;

// ========== //

// ========== PRAGMA ========== //

// Affichage du vecteur (variable globale) des fonctions à vérifier
static void print_fun_vec()
{
    tree x;
    printf("fun_vec contains %i element(s):", fun_vec->length());
    for (int i = 0; fun_vec->iterate(i, &x); i++)
        printf(" %s,", IDENTIFIER_POINTER(x));
    printf("\n");
}

// Traitement de la directive #pragma ProjetCA mpicoll_check
static void handle_pragma_mpicoll_check(cpp_reader *)
{
    location_t loc;
    enum cpp_ttype token;
    tree x;
    bool close_paren_needed_p = false;

    // Erreur si la directive est placée au sein d'une fonction
    if (cfun)
    {
        error_at(cfun->function_start_locus, "%<#pragma ProjetCA mpicoll_check%> is not allowed inside functions");
        return;
    }

    token = pragma_lex(&x, &loc);
    // Si la directive est suivie d'une parenthèse ouvrante, on cherche une liste de noms de fonctions de la forme (fun1,fun2,fun3,...)
    // Sinon, on s'attend au nom d'une seule fonction
    if (token == CPP_OPEN_PAREN)
    {
        close_paren_needed_p = true;
        token = pragma_lex(&x, &loc);
    }

    // Si le premier token (ou suivant la parenthèse) n'est pas un nom, on signale une erreur
    if (token != CPP_NAME)
        error_at(loc, "%<#pragma ProjetCA mpicoll_check%> is not a valid name");
    else
    {
        do
        {
            // On émet un avertissement si le nom d'une fonction est présent plusieurs fois dans l'ensemble des directives #pragma ProjetCA mpicoll_check
            if (fun_vec->contains(x))
                warning_at(loc, 0, "%<#pragma ProjetCA mpicoll_check%> already contains the function %<%s%>", IDENTIFIER_POINTER(x));
            // Sinon, on ajoute la fonction au vecteur
            else
                fun_vec->safe_push(x);

            // On parcourt la liste de noms de fonctions séparés par des virgules
            token = pragma_lex(&x, &loc);
            while (token == CPP_COMMA)
                token = pragma_lex(&x, &loc);
        } while (token == CPP_NAME);

        // On vérifie que la liste de noms de fonctions est bien terminée par une parenthèse fermante
        if (close_paren_needed_p)
        {
            if (token == CPP_CLOSE_PAREN)
                token = pragma_lex(&x, &loc);
            else
                error_at(loc, "%<#pragma ProjetCA mpicoll_check%> does not have a final %<)%>");
        }

        if (token != CPP_EOF)
        {
            error_at(loc, "%<#pragma ProjetCA mpicoll_check%> string is badly formed");
            return;
        }

        if (debug_mode)
            print_fun_vec();
    }
}

// Enregistrement de la directive #pragma ProjetCA mpicoll_check
static void register_pragma_mpicoll_check(void *event_data, void *data)
{
    c_register_pragma("ProjetCA", "mpicoll_check", handle_pragma_mpicoll_check);
}

// Opérations de clôture de la directive #pragma ProjetCA mpicoll_check
static void clear_pragma_mpicoll_check(void *event_data, void *data)
{
    tree x;
    // On émet un avertissement pour chaque fonction présente dans la directive qui n'a pas été appelée durant les passes
    for (int i = 0; fun_vec->iterate(i, &x); i++)
        warning(0, "%<#pragma ProjetCA mpicoll_check%> contains the function %<%s%> which does not seem defined", IDENTIFIER_POINTER(x));

    // On libère le vecteur
    fun_vec->release();
}

// ========== //

// ========== UTILS ========== //

// Récupération du code de l'opération collective MPI associée à l'instruction courante
// Si l'instruction courante n'est pas une opération collective MPI présente dans la liste, on renvoie LAST_AND_UNUSED_MPI_COLLECTIVE_CODE
enum mpi_collective_code get_mpi_collective_code(gimple *stmt)
{
    if (is_gimple_call(stmt))
    {
        const char *callee_name;

        callee_name = IDENTIFIER_POINTER(DECL_NAME(gimple_call_fndecl(stmt)));

        for (int i = 0; i < LAST_AND_UNUSED_MPI_COLLECTIVE_CODE; i++)
        {
            if (strcmp(callee_name, mpi_collective_name[i]) == 0)
            {
                return mpi_collective_code(i);
            }
        }
    }

    return LAST_AND_UNUSED_MPI_COLLECTIVE_CODE;
}

// Séparation des blocks contenant plusieurs appels MPI
void split_blocks_with_multiple_mpi_calls(function *fun)
{
    basic_block bb;

    // On parcourt tous les basic blocks de la fonction
    FOR_EACH_BB_FN(bb, fun)
    {
        gimple *old_stmt = NULL;

        for (gimple_stmt_iterator gsi = gsi_start_bb(bb); !gsi_end_p(gsi); gsi_next(&gsi))
        {
            gimple *stmt = gsi_stmt(gsi);

            mpi_collective_code stmt_code = get_mpi_collective_code(stmt);

            // On repère les instructions courantes qui sont des fonctions MPI collective présentes dans la liste
            if (stmt_code != LAST_AND_UNUSED_MPI_COLLECTIVE_CODE)
            {
                // Si on a déjà repéré une instruction MPI collective dans le basic block courant, on crée un nouveau basic block
                if (old_stmt != NULL)
                    split_block(bb, old_stmt);
                old_stmt = stmt;
            }
        }
    }
}

bitmap_head *generate_new_cfg_edges(function *fun)
{
    bitmap_head *new_cfg_edges = XNEWVEC(bitmap_head, n_basic_blocks_for_fn(fun));
    basic_block src = ENTRY_BLOCK_PTR_FOR_FN(fun);
    bitmap *visited_blocks;
    visited_blocks = XNEWVEC(bitmap, n_basic_blocks_for_fn(fun));
    edge e;
    basic_block bb;

    // On initialise le bitmap des arcs du nouveau CFG
    FOR_EACH_BB_FN(bb, fun)
    {
        bitmap_initialize(&new_cfg_edges[bb->index], &bitmap_default_obstack);
    }

    // On initialise le bitmap des bb déjà visités
    bitmap_initialize(*visited_blocks, &bitmap_default_obstack);

    // On marque le bloc d'entrée comme visité
    bitmap_set_bit(*visited_blocks, src->index);

    // On parcourt le CFG à partir du bloc d'entrée
    std::queue<basic_block> q;
    // Ajout du bloc d'entrée dans la file
    q.push(src);

    // Tant que la file n'est pas vide, on traite le premier élément de la file
    // On ajoute les arcs sortants dont le bloc de destination n'a pas encore été visité
    while (!q.empty())
    {
        basic_block bb = q.front();
        q.pop();

        edge_iterator ei;
        FOR_EACH_EDGE(e, ei, bb->succs)
        {
            basic_block succ = e->dest;

            if (!bitmap_bit_p(*visited_blocks, succ->index))
            {
                bitmap_set_bit(&new_cfg_edges[bb->index], succ->index);
                bitmap_set_bit(*visited_blocks, succ->index);
                q.push(succ);
            }
        }
    }

    // On libère le bitmap des bb déjà visités
    bitmap_clear(*visited_blocks);

    return new_cfg_edges;
}

// Calcul du rang maximal des bb d'une fonction
static int get_max_rank(function *fun, int *ranks)
{
    int max_rank = 0;
    for (int i = 0; i < n_basic_blocks_for_fn(fun); i++)
    {
        if (ranks[i] > max_rank)
        {
            max_rank = ranks[i];
        }
    }

    return max_rank;
}

// ========== //

// ========== GRAPHVIZ ========== //

// Création du nom du fichier .dot à partir du nom de la fonction et d'un suffixe
static char *cfgviz_generate_filename(function *fun, const char *suffix)
{
    char *target_filename;

    target_filename = (char *)xmalloc(1024 * sizeof(char));

    snprintf(target_filename, 1024, "%s_%s_%d_%s.dot",
             current_function_name(),
             LOCATION_FILE(fun->function_start_locus),
             LOCATION_LINE(fun->function_start_locus),
             suffix);

    return target_filename;
}

// Export de la représentation du CFG d'une fonction dans un descriptor de fichier
static void cfgviz_internal_dump(function *fun, FILE *out)
{
    basic_block bb;

    fprintf(out, "Digraph G{\n");

    FOR_ALL_BB_FN(bb, cfun)
    {
        fprintf(out, "%d [label=\"BB %d", bb->index, bb->index);

        gimple_stmt_iterator gsi;
        gimple *stmt;
        gsi = gsi_start_bb(bb);
        stmt = gsi_stmt(gsi);

        /* Itération sur les instructions du bloc */
        for (gsi = gsi_start_bb(bb); !gsi_end_p(gsi); gsi_next(&gsi))
        {
            stmt = gsi_stmt(gsi);

            enum mpi_collective_code returned_code = get_mpi_collective_code(stmt);

            if (returned_code != LAST_AND_UNUSED_MPI_COLLECTIVE_CODE)
            {
                fprintf(out, " \\n %s", mpi_collective_name[returned_code]);
            }
        }

        fprintf(out, "\" shape=ellipse]\n");

        edge_iterator eit;
        edge e;

        // Représentation des arcs sortants
        FOR_EACH_EDGE(e, eit, bb->succs)
        {
            const char *label = "";
            if (e->flags == EDGE_TRUE_VALUE)
                label = "true";
            else if (e->flags == EDGE_FALSE_VALUE)
                label = "false";

            fprintf(out, "%d -> %d [color=red label=\"%s\"]\n",
                    bb->index, e->dest->index, label);
        }
    }

    fprintf(out, "}\n");
}

// Export de la représentation du CFG d'une fonction dans un fichier .dot
void cfgviz_dump(function *fun, const char *suffix)
{
    char *target_filename;
    FILE *out;

    target_filename = cfgviz_generate_filename(fun, suffix);

    printf("Generating CFG of function %s in file <%s>\n",
           current_function_name(), target_filename);

    out = fopen(target_filename, "w");

    cfgviz_internal_dump(fun, out);

    fclose(out);
    free(target_filename);
}

// ========== //

// ========== DOMINANCE ========== //

// Calcul de la post dominance d'un ensemble de basic blocks
bitmap get_post_dominance_for_a_set(bitmap_head *set, function *fun, bitmap_head *pd)
{
    bitmap_initialize(pd, &bitmap_default_obstack);

    // Pour chaque bb de l'ensemble, on récupère tous les bb post-dominés par celui-ci
    basic_block bb;
    FOR_ALL_BB_FN(bb, fun)
    {
        if (bitmap_bit_p(set, bb->index))
        {
            auto_vec<basic_block> pd_blocks = get_all_dominated_blocks(CDI_POST_DOMINATORS, bb);
            for (unsigned int i = 0; i < pd_blocks.length(); i++)
            {
                bitmap_set_bit(pd, pd_blocks[i]->index);
            }
        }
    }

    // On garde les bb dont au moins un successeur est post-dominé par tous les bb de l'ensemble
    FOR_ALL_BB_FN(bb, fun)
    {
        edge e;
        edge_iterator ei;
        int total = 0;
        int succ_n = 0;
        FOR_EACH_EDGE(e, ei, bb->succs)
        {
            basic_block succ = e->dest;
            if (bitmap_bit_p(pd, succ->index))
                succ_n++;

            total++;
        }
        if (total > 0 && succ_n == total)
            bitmap_set_bit(pd, bb->index);
    }

    return pd;
}

// Calcul de la frontière de post dominance d'un ensemble de basic blocks
bitmap get_post_dominance_frontier_for_a_set(bitmap_head *set, function *fun, bitmap_head *pd)
{
    bitmap_head pd2;
    bitmap_initialize(pd, &bitmap_default_obstack);

    // On récupère la post dominance de l'ensemble
    get_post_dominance_for_a_set(set, fun, &pd2);

    // On garde les noeuds qui ne sont pas post-dominés par l'ensemble mais dont au moins un successeur l'est
    basic_block bb;
    FOR_ALL_BB_FN(bb, fun)
    {
        edge e;
        edge_iterator ei;
        FOR_EACH_EDGE(e, ei, bb->succs)
        {
            basic_block succ = e->dest;
            if (bitmap_bit_p(&pd2, succ->index) && !bitmap_bit_p(&pd2, bb->index))
            {
                bitmap_set_bit(pd, bb->index);
            }
        }
    }

    return pd;
}

// ========== //

// ========== PASS ========== //

const pass_data pass_mpicoll_check_data = {
    GIMPLE_PASS,
    "MPICOLL_CHECK",
    OPTGROUP_NONE,
    TV_OPTIMIZE,
    0,
    0,
    0,
    0,
    0,
};

class pass_mpicoll_check : public gimple_opt_pass
{
public:
    pass_mpicoll_check(gcc::context *ctxt) : gimple_opt_pass(pass_mpicoll_check_data, ctxt) {}

    pass_mpicoll_check *clone() { return new pass_mpicoll_check(g); }

    bool gate(function *fun)
    {
        bool pass_enabled = false;

        tree x;
        unsigned int i = 0;
        // On parcourt le vecteur des fonctions à vérifier
        while (!pass_enabled && i < fun_vec->length())
        {
            fun_vec->iterate(i, &x);
            i++;
            // Si la fonction courante est présente dans le vecteur, on l'enlève du vecteur et on active la passe
            if (strcmp(IDENTIFIER_POINTER(x), function_name(fun)) == 0)
            {
                fun_vec->unordered_remove(i - 1);
                pass_enabled = true;
            }
        }

        if (pass_enabled && debug_mode)
            printf("Executing mpicoll_check pass for the function %s\n", function_name(fun));

        return pass_enabled;
    }

    unsigned int execute(function *fun)
    {
        // Export du CFG de la fonction avant la séparation des blocs contenant plusieurs appels MPI
        if (debug_mode)
            cfgviz_dump(fun, "before_split");

        // Séparation des blocs contenant plusieurs appels MPI
        split_blocks_with_multiple_mpi_calls(fun);

        // Export du CFG de la fonction après la séparation des blocs contenant plusieurs appels MPI
        if (debug_mode)
            cfgviz_dump(fun, "after_split");

        // Calcul des informations de post-dominance
        calculate_dominance_info(CDI_POST_DOMINATORS);

        // Création du nouveau CFG en retirant les arcs retour
        bitmap_head *new_cfg_edges = generate_new_cfg_edges(fun);

        // Définition d'une structure pour stocker les informations de rang
        struct bb_with_rank
        {
            basic_block bb;
            int rank;
        };

        basic_block bb;

        std::queue<bb_with_rank> q;
        bb_with_rank bbr;

        bbr.bb = ENTRY_BLOCK_PTR_FOR_FN(fun);
        bbr.rank = 0;
        q.push(bbr);

        // Tableaux pour stocker les informations de rang et d'appel de chaque bb
        int calls[n_basic_blocks_for_fn(fun)];
        int ranks[n_basic_blocks_for_fn(fun)];

        // On parcourt l'ensemble des basic blocks de l'entrée vers la sortie
        while (!q.empty())
        {
            bbr = q.front();
            q.pop();

            gimple_stmt_iterator gsi;
            mpi_collective_code c = LAST_AND_UNUSED_MPI_COLLECTIVE_CODE;

            // Si le bb contient une instruction MPI, on sort de la boucle pour lui attribuer un rang
            for (gsi = gsi_start_bb(bbr.bb); !gsi_end_p(gsi); gsi_next(&gsi))
            {
                gimple *stmt = gsi_stmt(gsi);
                c = get_mpi_collective_code(stmt);
                if (c != LAST_AND_UNUSED_MPI_COLLECTIVE_CODE)
                    break;
            }

            calls[bbr.bb->index] = c;

            // Si le bb contient un appel MPI, on augmente d'un son rang par rapport à celui du prédécesseur
            // Sinon, on garde le même rang et on continue
            if (c != LAST_AND_UNUSED_MPI_COLLECTIVE_CODE)
                ranks[bbr.bb->index] = bbr.rank + 1;
            else
                ranks[bbr.bb->index] = bbr.rank;

            FOR_ALL_BB_FN(bb, fun)
            {
                // On ajoute les successeurs du bb courant dans la file en leur donnant le même rang
                if (bitmap_bit_p(&new_cfg_edges[bbr.bb->index], bb->index))
                {
                    bb_with_rank bbr2;
                    bbr2.bb = bb;
                    bbr2.rank = ranks[bbr.bb->index];
                    q.push(bbr2);
                }
            }
        }

        // Récupération du rang maximal
        int max_rank = get_max_rank(fun, ranks);

        // Initialisation d'une matrice de bitmaps de taille nombre_appels_differents * rang_maximum pour avoir tous les ensembles possibles
        bitmap_head **sets = XNEWVEC(bitmap_head *, max_rank);

        // Initialisation des bitmaps
        for (int i = 0; i < max_rank; i++)
        {
            sets[i] = XNEWVEC(bitmap_head, LAST_AND_UNUSED_MPI_COLLECTIVE_CODE);
            for (unsigned int j = 0; j < LAST_AND_UNUSED_MPI_COLLECTIVE_CODE; j++)
            {
                bitmap_initialize(&sets[i][j], &bitmap_default_obstack);
            }
        }

        // Remplissage des bitmaps avec les index des bb compris dans les ensembles correspondants
        FOR_ALL_BB_FN(bb, fun)
        {
            if (calls[bb->index] != LAST_AND_UNUSED_MPI_COLLECTIVE_CODE)
            {
                bitmap_set_bit(&sets[ranks[bb->index] - 1][calls[bb->index]], bb->index);
            }
        }

        // Pour chaque ensemble possible de notre matrice, on récupère la frontière de post dominance
        for (int i = 0; i < max_rank; i++)
        {
            for (unsigned int j = 0; j < LAST_AND_UNUSED_MPI_COLLECTIVE_CODE; j++)
            {
                bitmap_head pd;
                int target_rank = 0;
                get_post_dominance_frontier_for_a_set(&sets[i][j], fun, &pd);

                // Si la frontière de post dominance n'est pas vide, on émet un avertissement pour deadlock
                // Cela signifie que certains chemins du CFG ne passent pas forcément par cette collective MPI
                // Certains processus peuvent donc être bloqués en attendant que les autres processus atteignent cette collective MPI à un autre moment
                if (!bitmap_empty_p(&pd))
                {
                    // On émet un avertissement en indiquant la collective concernée dans la fonction
                    warning(0, "The MPI collective %<%s%> (rank %d) differs between process (possible deadlock)", mpi_collective_name[j], i + 1);
                    target_rank = i + 1;

                    bitmap_head temp;
                    bitmap_initialize(&temp, &bitmap_default_obstack);
                    // On calcule la frontière de post-dominance itérée jusqu'à ce qu'elle soit stable pour trouver l'origine du problème
                    do
                    {
                        bitmap_copy(&temp, &pd);
                        get_post_dominance_frontier_for_a_set(&temp, fun, &pd);
                    } while (!bitmap_empty_p(&pd));

                    // Notre frontière de post-dominance itérée est stable, on peut donc récupérer et indiquer le basic block contenant l'instruction à partir de laquelle on observe des divergences
                    for (int i = 0; i < n_basic_blocks_for_fn(fun); i++)
                    {
                        if (bitmap_bit_p(&temp, i))
                        {
                            bb = BASIC_BLOCK_FOR_FN(fun, i);

                            // On parcourt les statements du basic block pour trouver la première instruction non MPI qui pourrait créer la divergence
                            gimple_stmt_iterator gsi;
                            gimple *stmt;
                            for (gsi = gsi_start_bb(bb); !gsi_end_p(gsi); gsi_next(&gsi))
                            {
                                stmt = gsi_stmt(gsi);
                                if (get_mpi_collective_code(stmt) == LAST_AND_UNUSED_MPI_COLLECTIVE_CODE)
                                {
                                    warning_at(gimple_location(stmt), 0, "The deadlock origin for the MPI collective %<%s%> (rank %d) is probably here", mpi_collective_name[j], target_rank);
                                    break;
                                }
                            }
                        }
                    }
                }
            }
        }

        free_dominance_info(CDI_POST_DOMINATORS);

        return 0;
    }
};

// ========== //

// ========== PLUGIN ========== //

// Initialisation du plugin
int plugin_init(struct plugin_name_args *plugin_info, struct plugin_gcc_version *version)
{
    // On crée le vecteur qui contiendra la liste des fonctions à vérifier issue de la directive #pragma ProjetCA mpicoll_check
    fun_vec = new vec<tree>;
    fun_vec->create(0);

    struct register_pass_info pass_info;

    // On vérifie que la version de GCC est compatible avec le plugin
    if (!plugin_default_version_check(version, &gcc_version))
        return 1;

    pass_mpicoll_check p(g);
    pass_info.pass = &p;
    pass_info.reference_pass_name = "cfg";
    pass_info.ref_pass_instance_number = 0;
    pass_info.pos_op = PASS_POS_INSERT_AFTER;

    register_callback(plugin_info->base_name, PLUGIN_PASS_MANAGER_SETUP, NULL, &pass_info);

    register_callback(plugin_info->base_name, PLUGIN_PRAGMAS, register_pragma_mpicoll_check, NULL);

    register_callback(plugin_info->base_name, PLUGIN_FINISH, clear_pragma_mpicoll_check, NULL);

    return 0;
}

// ========== //