graph.c

Go to the documentation of this file.

/*
 
  $Id: graph.c 23065 2016-03-02 09:05:50Z coelho $
 
  Copyright 1989-2016 MINES ParisTech
 
  This file is part of PIPS.
 
  PIPS 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
  any later version.
 
  PIPS 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 PIPS.  If not, see <http://www.gnu.org/licenses/>.
 
*/
#ifdef HAVE_CONFIG_H
    #include "pips_config.h"
#endif
 
#include <stdio.h>
#include <strings.h>
 
#include "linear.h"
 
#include "genC.h"
#include "ri.h"
#include "text.h"
#include "text-util.h"
#include "database.h"
 
#include "misc.h"
#include "ri-util.h"
#include "resources.h"
#include "pipsdbm.h"
#include "control.h"
 
/* global mapping from statements to their control in the full control graph
 */
GENERIC_GLOBAL_FUNCTION(ctrl_graph, controlmap)
 
/* the crtl_graph is freed by hand, because the default behavior is
 * not convenient for my purpose. I would have needed a persistant
 * statement in the control, but it is not desired in pips.
 */
void clean_ctrl_graph()
{
    CONTROLMAP_MAP(s, c,
      {
          pips_debug(7, "statement (%td,%td)\n",
                     ORDERING_NUMBER(statement_ordering(s)),
                     ORDERING_STATEMENT(statement_ordering(s)));
 
          control_statement(c) = statement_undefined;
          gen_free_list(control_successors(c));
          control_successors(c) = NIL;
          gen_free_list(control_predecessors(c));
          control_predecessors(c) = NIL;
      },
          get_ctrl_graph());
 
    close_ctrl_graph(); /* now it can be freed safely */
}
 
/*  add (s1) --> (s2),
 *  that is s2 as successor of s1 and s1 as predecessor of s2.
 *  last added put in first place.
 *  this property is used for a depth first enumeration.
 */
static void
add_arrow_in_ctrl_graph(statement s1, statement s2)
{
    control
        c1 = load_ctrl_graph(s1),
        c2 = load_ctrl_graph(s2);
 
    pips_debug(7, "(%td,%td:%td) -> (%td,%td;%td)\n",
               ORDERING_NUMBER(statement_ordering(s1)),
               ORDERING_STATEMENT(statement_ordering(s1)),
               statement_number(s1),
               ORDERING_NUMBER(statement_ordering(s2)),
               ORDERING_STATEMENT(statement_ordering(s2)),
               statement_number(s2));
 
    control_successors(c1) = gen_once(c2, control_successors(c1));
    control_predecessors(c2) = gen_once(c1, control_predecessors(c2));
}
 
static void add_arrows_in_ctrl_graph(statement s, /* statement */ list l)
{
    for(; !ENDP(l); l=CDR(l))
        add_arrow_in_ctrl_graph(s, STATEMENT(CAR(l)));
}
 
list /* of statement */
control_list_to_statement_list(/* control */ list lc)
{
    list /* of statements */ ls = NIL;
    MAP(CONTROL, c, ls = CONS(STATEMENT, control_statement(c), ls), lc);
    return ls;
}
 
static void statement_arrows(statement s, /* statement */ list next)
{
    instruction i = statement_instruction(s);
    tag t = instruction_tag(i);
 
    switch(t)
    {
    case is_instruction_block:
    {
        statement current, succ;
        list /* of statements */
            l = instruction_block(i),
            just_next;
 
        if (ENDP(l))
        {
            add_arrows_in_ctrl_graph(s, next);
            return;
        }
        /* else
         */
        add_arrow_in_ctrl_graph(s, STATEMENT(CAR(l)));
 
        for(current = STATEMENT(CAR(l)),
              l = CDR(l),
              succ = ENDP(l) ? statement_undefined : STATEMENT(CAR(l)),
              just_next = CONS(STATEMENT, succ, NIL);
            !ENDP(l);
            current = succ,
              l = CDR(l),
              succ = ENDP(l) ? statement_undefined : STATEMENT(CAR(l)),
              STATEMENT_(CAR(just_next)) = succ)
        {
            statement_arrows(current, just_next);
        }
 
        gen_free_list(just_next), just_next=NIL;
 
        statement_arrows(current, next);
        break;
    }
    case is_instruction_test:
    {
        test
            x = instruction_test(i);
        statement
            strue = test_true(x),
            sfalse = test_false(x);
 
        add_arrow_in_ctrl_graph(s, sfalse),
        statement_arrows(sfalse, next);
 
        add_arrow_in_ctrl_graph(s, strue), /* true is before false */
        statement_arrows(strue, next);
 
        break;
    }
    case is_instruction_whileloop:
    case is_instruction_loop:
    {
        statement b;
        list /* of statements */ just_next =
            gen_nconc(gen_copy_seq(next), CONS(STATEMENT, s, NIL));
 
        if(instruction_loop_p(i)) {
            loop l = instruction_loop(i);
            b = loop_body(l);
        }
        else {
            whileloop l = instruction_whileloop(i);
            b = whileloop_body(l);
        }
 
        add_arrows_in_ctrl_graph(s, next); /* no iteration */
        add_arrow_in_ctrl_graph(s, b);     /* some iterations, first */
 
        statement_arrows(b, just_next);
 
        gen_free_list(just_next), just_next=NIL;
 
        break;
    }
    case is_instruction_call:
        add_arrows_in_ctrl_graph(s, next);
        break;
    case is_instruction_unstructured:
    {
        unstructured u = instruction_unstructured(i);
        list /* of statements */
            blocks = NIL,
            lstat = NIL;
        statement x;
        control c_in = unstructured_control(u);
 
        add_arrow_in_ctrl_graph(s, control_statement(c_in));
 
        /* hmmm... I'm not too confident in this loop.
         * ??? what should be done with next?
         * ??? should I trust the graph? I hope I can.
         */
        CONTROL_MAP(c,
                {
                    x = control_statement(c);
                    lstat = control_list_to_statement_list
                        (control_successors(c));
 
                    statement_arrows(x, lstat);
                    gen_free_list(lstat);
                },
                    c_in,
                    blocks);
 
        gen_free_list(blocks);
 
        break;
    }
    case is_instruction_goto:
    default:
        pips_internal_error("unexpected instruction tag (%d)", t);
    }
}
 
static void stmt_rewrite(statement s)
{
    if (!bound_ctrl_graph_p(s))
        store_ctrl_graph(s, make_control(s, NIL, NIL));
}
 
void build_full_ctrl_graph(statement s)
{
    pips_debug(3, "statement (%td,%td:%td)\n",
               ORDERING_NUMBER(statement_ordering(s)),
               ORDERING_STATEMENT(statement_ordering(s)),
               statement_number(s));
 
    /*  first pass to initialize the ctrl_graph controls
     */
    init_ctrl_graph();
    gen_multi_recurse(s,
                      statement_domain, gen_true, stmt_rewrite, /* STATEMENT */
                      NULL);
 
    /*  second pass to link the statements
     */
    statement_arrows(s, NIL);
}
 
/* FULL CONTROL GRAPH for module NAME
 */
void full_control_graph(string name)
{
    statement s = (statement) db_get_memory_resource(DBR_CODE, name, true);
    build_full_ctrl_graph(s);
 
    /*  should put something in the db if made as a pass
     */
}
 
/* TRAVELLING on the control graph
 *
 * init, next, close functions.
 * - the init function is given a starting point (statement) s and a
 *   decision function decision. The function should say whether to
 *   go on with the successors of its arguments.
 * - the next function gives the next visited statement.
 * - the close function frees the static data.
 */
 
#ifndef bool_undefined
    #define bool_undefined ((bool) (-15))
    #define bool_undefined_p(b) ((b)==bool_undefined)
#endif
 
/* Static data for the travel.
 * - the stack stores the statements to see
 * - the mapping stores the already stacked statements
 * - decision function...
 */
DEFINE_LOCAL_STACK(to_see, statement)
GENERIC_LOCAL_MAPPING(stacked, bool, statement)
static bool (*travel_decision)(statement);
 
static void push_if_necessary(statement s)
{
  if (load_statement_stacked(s)!=true)
  {
    to_see_push(s);
    store_statement_stacked(s, true);
  }
}
 
/* it is pushed in *reverse* order to preserve the depth first view.
 */
static void push(/* control */ list l)
{
    if (!ENDP(l))
        push(CDR(l)),
        push_if_necessary(control_statement(CONTROL(CAR(l))));
}
 
static void push_successors(statement s)
{
    push(control_successors(load_ctrl_graph(s)));
}
 
void init_ctrl_graph_travel(statement s, bool (*decision)(statement))
{
    make_to_see_stack();             /* initializations */
    make_stacked_map();
    travel_decision = decision;
 
    store_statement_stacked(s, true); /* no loop back */
    push_successors(s);
}
 
bool next_ctrl_graph_travel(statement *ps)
{
    while (!to_see_empty_p())
    {
        *ps = to_see_pop();
        if ((*travel_decision)(*ps))
        {
            push_successors(*ps);
            return true;
        }
    }
 
    return false;
}
 
void close_ctrl_graph_travel(void)
{
    free_to_see_stack();
    free_stacked_map();
}
 
/*  That's all
 */