toposort.c File Reference

#include <stdio.h>
#include <string.h>
#include "genC.h"
#include "linear.h"
#include "misc.h"
#include "pipsdbm.h"
#include "ri.h"
#include "ri-util.h"
#include "icfg.h"

Include dependency graph for toposort.c:

Go to the source code of this file.

Functions
list	module_name_to_callees (char *module_name) const
	toposort.c More...
list	module_to_callees (entity mod)
void	topological_number_assign_to_module (hash_table hash_module_to_depth, entity mod, size_t n)
list	module_list_sort (hash_table hash_module_to_depth, list current_list, entity mod, size_t n)
list	topologically_sorted_module_list (entity mod)
void	print_module_name_to_toposorts (char *module_name) const

Function Documentation

module_list_sort()

list module_list_sort	(	hash_table	hash_module_to_depth,
		list	current_list,
		entity	mod,
		size_t	n
	)

create the callees list whose caller has the depth n

free the same_depth_list for later use

create same_depth_list whose depth is n+1

concatenate former current_list with same_depth_list

use module_list_sort recursively

Parameters

hash_module_to_depth	ash_module_to_depth
current_list	urrent_list
mod	od

Definition at line 123 of file toposort.c.

{
    list callees_list = NIL;
    static list same_depth_list = NIL;
    size_t depth;
 
    /* create the callees list whose caller has the depth n */
    if ( same_depth_list == NIL )
        callees_list = module_to_callees(mod);
    else {
        MAPL(pm,{ entity e = ENTITY(CAR(pm));
                  callees_list = gen_nconc(callees_list,
                                           gen_copy_seq(module_to_callees(e)));
                },
             same_depth_list);
    }
 
    /* free the same_depth_list for later use */
 
    same_depth_list = NIL;
 
    /* create same_depth_list whose depth is n+1 */
    if ( callees_list != NIL ) {
        MAPL(pm,{ entity e = ENTITY(CAR(pm));
                  depth = (size_t) hash_get(hash_module_to_depth, (char *) e);
                  if ( depth == n+1 ) {
                      same_depth_list = gen_nconc(same_depth_list,
                                             CONS(ENTITY, e, NIL));
                      hash_put(hash_module_to_depth,
                               (char *) e, (char *) -1);
                  }
                },
             callees_list);
 
        /* concatenate former current_list with same_depth_list */
        current_list = gen_nconc(current_list, same_depth_list);
 
        /* use module_list_sort recursively */
        current_list = module_list_sort(hash_module_to_depth, 
                                           current_list,
                                           ENTITY(CAR(same_depth_list)), 
                                           n+1);
    }
    return (current_list);
}

References CAR, CONS, depth, ENTITY, gen_copy_seq(), gen_nconc(), hash_get(), hash_put(), MAPL, module_list_sort(), module_to_callees(), and NIL.

Referenced by module_list_sort(), and topologically_sorted_module_list().

Here is the call graph for this function:

Here is the caller graph for this function:

module_name_to_callees()

list module_name_to_callees

(

char*

module_name

)

const

toposort.c

Entry point: list topologically_sorted_module_list(mod)

returns the list of subroutines/functions called in the module mod sorted as follow: we recursively build the graph of calls, taking mod for root, and we apply on it the topological sort. The first of the list is the module mod itself.

Pierre Berthomier, May 1990 Lei Zhou, January 1991 get all the callees of the module module_name,return the no-empty list of string. if the module has callee(s),the first element of the return list is the module's last callee.

Definition at line 59 of file toposort.c.

{
    callees cl;
    static hash_table hash_table_to_callees_string;
    static bool hash_table_is_created = false;
    list callees_list=NIL;
 
    cl = (callees)db_get_memory_resource(DBR_CALLEES,module_name,true);
 
    if ( !hash_table_is_created ) {
        hash_table_to_callees_string = hash_table_make(hash_pointer, 0);
        hash_table_is_created = true;
    }
    
    callees_list = (list)hash_get(hash_table_to_callees_string, module_name);
 
    if ( callees_list == (list)HASH_UNDEFINED_VALUE ) {
        callees_list = callees_callees(cl);
        hash_put(hash_table_to_callees_string, module_name, 
                 (char *)callees_list);
    }
 
    return(callees_list);
}

References callees_callees, db_get_memory_resource(), hash_get(), hash_pointer, hash_put(), hash_table_make(), HASH_UNDEFINED_VALUE, module_name(), and NIL.

Here is the call graph for this function:

module_to_callees()

list module_to_callees

(

entity

mod

)

Parameters

mod

od

Definition at line 85 of file toposort.c.

{
    list return_list = NIL;
    list callees_list = code_declarations(entity_code(mod));
    
    MAPL(ce,{
        entity e = ENTITY(CAR(ce));
        if ( type_functional_p(entity_type(e)) )
            return_list = CONS(ENTITY, 
                               local_name_to_top_level_entity(entity_local_name(e)),
                               return_list);
    },callees_list);
 
    return(return_list);
}

References CAR, code_declarations, CONS, ENTITY, entity_code(), entity_local_name(), entity_type, local_name_to_top_level_entity(), MAPL, NIL, and type_functional_p.

Referenced by module_list_sort(), and topological_number_assign_to_module().

Here is the call graph for this function:

Here is the caller graph for this function:

print_module_name_to_toposorts()

void print_module_name_to_toposorts

(

char*

module_name

)

const

Definition at line 195 of file toposort.c.

{
    list sorted_list = NIL;
    string filename;
    FILE *fp;
    entity mod = local_name_to_top_level_entity(module_name);
 
    pips_assert("print_module_name_to_toposorts", mod != entity_undefined &&
                entity_module_p(mod));
 
    fprintf(stderr, "topological-sorting callees for %s ...\n",
            entity_name(mod));
 
    debug_on(ICFG_DEBUG_LEVEL);
 
    sorted_list = (list) topologically_sorted_module_list(mod);
    filename = strdup(concatenate(db_get_current_workspace_directory(), 
                                  "/", module_name, ".topo",NULL));
 
    fp = safe_fopen(filename, "w");
 
    MAPL(pm,
         { fprintf(fp, "%s\n",entity_name(ENTITY(CAR(pm)))); },
         sorted_list);
 
    safe_fclose(fp, filename);
    fprintf(stderr, "result written to %s\n", filename);
 
    debug_off();
}

References CAR, concatenate(), db_get_current_workspace_directory(), debug_off, debug_on, ENTITY, entity_module_p(), entity_name, entity_undefined, fprintf(), ICFG_DEBUG_LEVEL, local_name_to_top_level_entity(), MAPL, module_name(), NIL, pips_assert, safe_fclose(), safe_fopen(), strdup(), and topologically_sorted_module_list().

Here is the call graph for this function:

topological_number_assign_to_module()

void topological_number_assign_to_module	(	hash_table	hash_module_to_depth,
		entity	mod,
		size_t	n
	)

assigns depth n+1 to callees of current module

Parameters

hash_module_to_depth	ash_module_to_depth
mod	od

Definition at line 102 of file toposort.c.

{
    size_t depth = (size_t) hash_get(hash_module_to_depth, (char *) mod);
    list callees_list = module_to_callees(mod);
 
    if ((depth == (size_t) ICFG_NOT_FOUND) || (depth < n))
        hash_put(hash_module_to_depth, (char *) mod, (char *) n);
              
    if ( callees_list != NIL ) {
    /* assigns depth n+1 to callees of current module */
        MAPL(pm,
            { entity e = ENTITY(CAR(pm));
              topological_number_assign_to_module(hash_module_to_depth, e, n+1);
            },
         callees_list);
    }
}

References CAR, depth, ENTITY, hash_get(), hash_put(), ICFG_NOT_FOUND, MAPL, module_to_callees(), NIL, and topological_number_assign_to_module().

Referenced by topological_number_assign_to_module(), and topologically_sorted_module_list().

Here is the call graph for this function:

Here is the caller graph for this function:

topologically_sorted_module_list()

list topologically_sorted_module_list

(

entity

mod

)

"depth" of subroutine or function for topological sort

Parameters

mod

od

Definition at line 173 of file toposort.c.

{
    /* "depth" of subroutine or function for topological sort */
    hash_table hash_module_to_depth = (hash_table) NULL;
    list sorted_list;
    
    hash_module_to_depth = hash_table_make(hash_pointer, 0);
    hash_dont_warn_on_redefinition();
 
    topological_number_assign_to_module(hash_module_to_depth, mod, 0);
 
    sorted_list = module_list_sort(hash_module_to_depth, NIL, mod, 0);
 
    pips_assert("free_hash_table",
                hash_module_to_depth != (hash_table) NULL);
    hash_table_free(hash_module_to_depth);
    hash_module_to_depth = (hash_table) NULL;
 
    return (sorted_list);
} 

References hash_dont_warn_on_redefinition(), hash_pointer, hash_table_free(), hash_table_make(), module_list_sort(), NIL, pips_assert, and topological_number_assign_to_module().

Referenced by print_module_name_to_toposorts().

Here is the call graph for this function:

Here is the caller graph for this function: