graph.c File Reference

#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"

Include dependency graph for graph.c:

Go to the source code of this file.

Macros
#define	bool_undefined   ((bool) (-15))
	TRAVELLING on the control graph. More...
#define	bool_undefined_p(b)   ((b)==bool_undefined)

Functions
void	clean_ctrl_graph ()
	global mapping from statements to their control in the full control graph More...
static void	add_arrow_in_ctrl_graph (statement s1, statement s2)
	add (s1) --> (s2), that is s2 as successor of s1 and s1 as predecessor of s2. More...
static void	add_arrows_in_ctrl_graph (statement s, list l)
list	control_list_to_statement_list (list lc)
	of statement More...
static void	statement_arrows (statement s, list next)
static void	stmt_rewrite (statement s)
void	build_full_ctrl_graph (statement s)
void	full_control_graph (string name)
	FULL CONTROL GRAPH for module NAME. More...
static void	push_if_necessary (statement s)
static void	push (list l)
	it is pushed in reverse order to preserve the depth first view. More...
static void	push_successors (statement s)
void	init_ctrl_graph_travel (statement s, bool(*decision)(statement))
bool	next_ctrl_graph_travel (statement *ps)
void	close_ctrl_graph_travel (void)

Variables
static bool(*	travel_decision )(statement)
	Static data for the travel. More...

Macro Definition Documentation

bool_undefined

#define bool_undefined   ((bool) (-15))

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.

Definition at line 279 of file graph.c.

bool_undefined_p

#define bool_undefined_p

(

b

)

((b)==bool_undefined)

Definition at line 280 of file graph.c.

Function Documentation

add_arrow_in_ctrl_graph()

static void add_arrow_in_ctrl_graph ( statement  s1, statement  s2  )

static

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.

Definition at line 78 of file graph.c.

{
    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));
}

References control_predecessors, control_successors, gen_once(), load_ctrl_graph(), ORDERING_NUMBER, ORDERING_STATEMENT, pips_debug, s1, statement_number, and statement_ordering.

Referenced by add_arrows_in_ctrl_graph(), and statement_arrows().

Here is the call graph for this function:

Here is the caller graph for this function:

add_arrows_in_ctrl_graph()

static void add_arrows_in_ctrl_graph ( statement  s, list  l  )

static

Parameters

l

statement

Definition at line 96 of file graph.c.

{
    for(; !ENDP(l); l=CDR(l))
        add_arrow_in_ctrl_graph(s, STATEMENT(CAR(l)));
}

References add_arrow_in_ctrl_graph(), CAR, CDR, ENDP, and STATEMENT.

Referenced by statement_arrows().

Here is the call graph for this function:

Here is the caller graph for this function:

build_full_ctrl_graph()

void build_full_ctrl_graph

(

statement

s

)

first pass to initialize the ctrl_graph controls

STATEMENT

second pass to link the statements

Definition at line 238 of file graph.c.

{
    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);
}

References gen_multi_recurse(), gen_true(), init_ctrl_graph(), NIL, ORDERING_NUMBER, ORDERING_STATEMENT, pips_debug, statement_arrows(), statement_domain, statement_number, statement_ordering, and stmt_rewrite().

Referenced by full_control_graph(), and handle_hpf_directives().

Here is the call graph for this function:

Here is the caller graph for this function:

clean_ctrl_graph()

void clean_ctrl_graph

(

void

)

global mapping from statements to their control in the full control graph

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.

now it can be freed safely

Definition at line 53 of file graph.c.

{
    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 */
}

References close_ctrl_graph(), control_predecessors, control_statement, control_successors, CONTROLMAP_MAP, gen_free_list(), get_ctrl_graph(), NIL, ORDERING_NUMBER, ORDERING_STATEMENT, pips_debug, statement_ordering, and statement_undefined.

Referenced by handle_hpf_directives().

Here is the call graph for this function:

Here is the caller graph for this function:

close_ctrl_graph_travel()

void close_ctrl_graph_travel

(

void

)

Definition at line 340 of file graph.c.

{
    free_to_see_stack();
    free_stacked_map();
}

Referenced by handle_independent_directive(), handle_reduction_directive(), and propagate_synonym().

Here is the caller graph for this function:

control_list_to_statement_list()

list control_list_to_statement_list

(

list

lc

)

of statement

of statements

Parameters

lc

control

Definition at line 103 of file graph.c.

{
    list /* of statements */ ls = NIL;
    MAP(CONTROL, c, ls = CONS(STATEMENT, control_statement(c), ls), lc);
    return ls;
}

References CONS, CONTROL, control_statement, MAP, NIL, and STATEMENT.

Referenced by compute_cumulated_reductions(), and statement_arrows().

Here is the caller graph for this function:

full_control_graph()

void full_control_graph

(

string

name

)

FULL CONTROL GRAPH for module NAME.

should put something in the db if made as a pass

Parameters

name

ame

Definition at line 259 of file graph.c.

{
    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
     */
}

References build_full_ctrl_graph(), and db_get_memory_resource().

Here is the call graph for this function:

init_ctrl_graph_travel()

void init_ctrl_graph_travel	(	statement	s,
		bool(*)(statement)	decision
	)

initializations

no loop back

Definition at line 315 of file graph.c.

{
    make_to_see_stack();             /* initializations */
    make_stacked_map();
    travel_decision = decision;
 
    store_statement_stacked(s, true); /* no loop back */
    push_successors(s);
}

References push_successors(), and travel_decision.

Referenced by handle_independent_directive(), handle_reduction_directive(), and propagate_synonym().

Here is the call graph for this function:

Here is the caller graph for this function:

next_ctrl_graph_travel()

bool next_ctrl_graph_travel

(

statement *

ps

)

Parameters

ps

s

Definition at line 325 of file graph.c.

{
    while (!to_see_empty_p())
    {
        *ps = to_see_pop();
        if ((*travel_decision)(*ps))
        {
            push_successors(*ps);
            return true;
        }
    }
 
    return false;
}

References push_successors(), and travel_decision.

Referenced by handle_independent_directive(), handle_reduction_directive(), and propagate_synonym().

Here is the call graph for this function:

Here is the caller graph for this function:

push()

static void push ( list  l )

static

it is pushed in reverse order to preserve the depth first view.

Parameters

l

control

Definition at line 303 of file graph.c.

{
    if (!ENDP(l))
        push(CDR(l)),
        push_if_necessary(control_statement(CONTROL(CAR(l))));
}

References CAR, CDR, CONTROL, control_statement, ENDP, and push_if_necessary().

Referenced by push_successors().

Here is the call graph for this function:

Here is the caller graph for this function:

push_if_necessary()

static void push_if_necessary ( statement  s )

static

Definition at line 292 of file graph.c.

{
  if (load_statement_stacked(s)!=true)
  {
    to_see_push(s);
    store_statement_stacked(s, true);
  }
}

Referenced by push().

Here is the caller graph for this function:

push_successors()

static void push_successors ( statement  s )

static

Definition at line 310 of file graph.c.

{
    push(control_successors(load_ctrl_graph(s)));
}

References control_successors, load_ctrl_graph(), and push().

Referenced by init_ctrl_graph_travel(), and next_ctrl_graph_travel().

Here is the call graph for this function:

Here is the caller graph for this function:

statement_arrows()

static void statement_arrows ( statement  s, list  next  )

static

of statements

else

true is before false

of statements

no iteration

some iterations, first

of statements

hmmm... I'm not too confident in this loop. ??? what should be done with next? ??? should I trust the graph? I hope I can.

Parameters

next

statement

Definition at line 110 of file graph.c.

{
    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);
    }
}

References add_arrow_in_ctrl_graph(), add_arrows_in_ctrl_graph(), blocks, c_in, CAR, CDR, CONS, control_list_to_statement_list(), CONTROL_MAP, control_statement, control_successors, current, ENDP, gen_copy_seq(), gen_free_list(), gen_nconc(), instruction_block, instruction_loop, instruction_loop_p, instruction_tag, instruction_test, instruction_unstructured, instruction_whileloop, is_instruction_block, is_instruction_call, is_instruction_goto, is_instruction_loop, is_instruction_test, is_instruction_unstructured, is_instruction_whileloop, loop_body, NIL, pips_internal_error, STATEMENT, STATEMENT_, statement_instruction, statement_undefined, test_false, test_true, unstructured_control, whileloop_body, and x.

Referenced by build_full_ctrl_graph().

Here is the call graph for this function:

Here is the caller graph for this function:

stmt_rewrite()

static void stmt_rewrite ( statement  s )

static

Definition at line 232 of file graph.c.

{
    if (!bound_ctrl_graph_p(s))
        store_ctrl_graph(s, make_control(s, NIL, NIL));
}

References bound_ctrl_graph_p(), make_control(), NIL, and store_ctrl_graph().

Referenced by build_full_ctrl_graph(), and drop_dummy_loops().

Here is the call graph for this function:

Here is the caller graph for this function:

Variable Documentation

travel_decision

bool(* travel_decision) (statement) ( statement  )

static

Static data for the travel.

• the stack stores the statements to see
• the mapping stores the already stacked statements
• decision function...

Definition at line 290 of file graph.c.

Referenced by init_ctrl_graph_travel(), and next_ctrl_graph_travel().