comp_unstr.c File Reference

#include <stdio.h>
#include <math.h>
#include "linear.h"
#include "genC.h"
#include "ri.h"
#include "effects.h"
#include "complexity_ri.h"
#include "ri-util.h"
#include "effects-util.h"
#include "properties.h"
#include "misc.h"
#include "matrice.h"
#include "complexity.h"

Include dependency graph for comp_unstr.c:

Go to the source code of this file.

Macros
#define	FA(i, j)   fa[(i)*n_controls + (j)]
	comp_unstr.c More...

Functions
complexity	unstructured_to_complexity (unstructured unstr, transformer precond, list effects_list)
	6th element of instruction More...
void	controls_to_hash_table (control cont, int *pn_controls, control_array, hash_table hash_control_to_complexity, transformer precond, list effects_list)
	Returns the hash table hash_control_to_complexity filled in with the complexities of the successors of control cont. More...
int	control_element_position_in_control_array (control cont, control_array, int n_controls)
	return the number i, that is i'th element of the control array Note that i begins from 1 instead of 0 More...
matrice	average_probability_matrix (unstructured unstr, int n_controls, control_array)
void	node_successors_to_matrix (control cont, matrice P, int n_controls, control_array, already_examined)
	On return, Pij = 1 <=> there's an edge from control #i to #j It means that every succeccor has the same possibility to be reached. More...

Variables
hash_table	hash_callee_to_complexity
	comp_expr_to_pnome.c More...
hash_table	hash_complexity_parameters

Macro Definition Documentation

FA

#define FA	(		i,
			j
	)		fa[(i)*n_controls + (j)]

comp_unstr.c

evaluate the complexity of unstructured graphs of statements used by get_bool_property
Added by AP, March 15th 93: allows the simulation of a two-dimensional array with a mono-dimensional memory allocation.

Definition at line 50 of file comp_unstr.c.

Function Documentation

average_probability_matrix()

matrice average_probability_matrix	(	unstructured	unstr,
		int	n_controls,
		control_array
	)

initilize the already_examined to false

make in P the matrix "is_successor_of"

we'll attribute equitable probabilities to the n succ. of a node

computes probabilities (0<=p<1) out of the matrix "is_successor_of"

Definition at line 270 of file comp_unstr.c.

{
    control cont = unstructured_control(unstr);
    bool already_examined[MAX_CONTROLS_IN_UNSTRUCTURED];
    int i, j , n_succs, max_n_succs = 0;
    matrice P = matrice_new(n_controls, n_controls);
 
    if ( n_controls > MAX_CONTROLS_IN_UNSTRUCTURED ) {
        pips_internal_error("control number is larger than %d", 
                   MAX_CONTROLS_IN_UNSTRUCTURED );
    }
 
    matrice_nulle(P, n_controls, n_controls);
 
    /* initilize the already_examined to false */
    for (i=1; i<=n_controls; i++) 
        already_examined[i] = false;
 
    /* make in P the matrix "is_successor_of" */
    node_successors_to_matrix(cont, P, n_controls,
                              control_array, already_examined);
 
    /* we'll attribute equitable probabilities to the n succ. of a node */
    for (i=1; i<=n_controls; i++) {
        n_succs = 0;
        for (j=1; j<=n_controls; j++)
        { 
            Value a = ACCESS(P, n_controls, i, j);
            n_succs += VALUE_TO_INT(a);
        }
        if (n_succs > max_n_succs) 
            max_n_succs = n_succs;
    }
 
    if (get_bool_property("COMPLEXITY_INTERMEDIATES")) {
        fprintf(stderr, "n_controls=%d, and max_n_succs=%d\n",
                n_controls,max_n_succs);
    }
 
    /* computes probabilities (0<=p<1) out of the matrix "is_successor_of" */
 
    
    DENOMINATOR(P) = int_to_value(factorielle(max_n_succs));
 
    for (i=1; i<=n_controls; i++) {
        n_succs = 0;
        for (j=1; j<=n_controls; j++) {
            Value a = ACCESS(P, n_controls, i, j);
            n_succs += VALUE_TO_INT(a);
        }
        if (n_succs>0)
            for (j=1; j<=n_controls; j++)
            {
                Value x = value_div(DENOMINATOR(P),int_to_value(n_succs));
                value_product(ACCESS(P, n_controls, i, j),x) ; 
            }
    }
 
    matrice_normalize(P, n_controls, n_controls);
 
    if (get_debug_level() > 0) {
        fprintf(stderr, "n_controls is %d\n", n_controls);
        fprintf(stderr, "average_probability_matrix:  P =\n");
        matrice_fprint(stderr, P, n_controls, n_controls);
    }
 
    return (P);
}

References ACCESS, DENOMINATOR, factorielle(), fprintf(), get_bool_property(), get_debug_level(), int_to_value, matrice_fprint(), matrice_new, matrice_normalize(), matrice_nulle(), MAX_CONTROLS_IN_UNSTRUCTURED, node_successors_to_matrix(), pips_internal_error, unstructured_control, value_div, value_product, VALUE_TO_INT, and x.

Referenced by unstructured_to_complexity().

Here is the call graph for this function:

Here is the caller graph for this function:

control_element_position_in_control_array()

int control_element_position_in_control_array	(	control	cont,
		control_array	,
		int	n_controls
	)

return the number i, that is i'th element of the control array Note that i begins from 1 instead of 0

In order to satisfy compiler. LZ 3 Feb. 93

Definition at line 253 of file comp_unstr.c.

{
    int i;
    
    for (i=1; i<=n_controls; i++)
        if (cont == control_array[i]) 
            return (i);
    pips_internal_error("this control isn't in control_array[]!");
 
    /* In order to satisfy compiler. LZ 3 Feb. 93 */
    return (i);
}

References pips_internal_error.

Referenced by node_successors_to_matrix().

Here is the caller graph for this function:

controls_to_hash_table()

void controls_to_hash_table	(	control	cont,
		int *	pn_controls,
		control_array	,
		hash_table	hash_control_to_complexity,
		transformer	precond,
		list	effects_list
	)

Returns the hash table hash_control_to_complexity filled in with the complexities of the successors of control cont.

each control of the graph is also stored in the array control_array (beginning at 1). also returns the total number of controls in the unstructured

Definition at line 212 of file comp_unstr.c.

{
    statement s = control_statement(cont);
    complexity comp;
 
    comp = statement_to_complexity(s, precond, effects_list);
    hash_put(hash_control_to_complexity, (char *) cont, (char *) comp);
    control_array[++(*pn_controls)] = cont;
    complexity_check_and_warn("control_to_complexity", comp);
 
    if (get_debug_level() >= 5) {
        fprintf(stderr, "this control($%p) has:", cont);
        complexity_fprint(stderr, comp, true, true);
        MAPL(pc, {
            fprintf(stderr, "successor: $%p\n", CONTROL(CAR(pc)));
            }, control_successors(cont));
        if ( control_successors(cont) == NIL )
            fprintf(stderr, "NO successor at all!\n");
        fprintf(stderr, ". . . . . . . . . . . . . . . . . . . . . .\n");
    }
 
    MAPL(pc, {
        control c = CONTROL(CAR(pc));
        if ( hash_get(hash_control_to_complexity, (char *) c)
            ==HASH_UNDEFINED_VALUE )
            controls_to_hash_table(c, pn_controls, control_array,
                                   hash_control_to_complexity, precond,
                                   effects_list);
    }, control_successors(cont));
}

References CAR, complexity_check_and_warn(), complexity_fprint(), CONTROL, control_statement, control_successors, fprintf(), get_debug_level(), hash_get(), hash_put(), HASH_UNDEFINED_VALUE, MAPL, NIL, and statement_to_complexity().

Referenced by unstructured_to_complexity().

Here is the call graph for this function:

Here is the caller graph for this function:

node_successors_to_matrix()

void node_successors_to_matrix	(	control	cont,
		matrice	P,
		int	n_controls,
		control_array	,
		already_examined
	)

On return, Pij = 1 <=> there's an edge from control #i to #j It means that every succeccor has the same possibility to be reached.

Modification:

• put already_examined[i] = true out of MAPL. If control i has several successors, there is no need to set it several times in MAPL. LZ 13/04/92

Here, we give equal possibility , 1 for each one

Definition at line 351 of file comp_unstr.c.

{
    int i = control_element_position_in_control_array(cont, control_array, n_controls);
 
    already_examined[i] = true;
 
    if (get_bool_property("COMPLEXITY_INTERMEDIATES")) {
        fprintf(stderr, "CONTROL ($%p)  CONTROL_NUMBER %d\n", cont, i);
    }
 
    MAPL(pc, {
        control succ = CONTROL(CAR(pc));
        int j = control_element_position_in_control_array(succ, control_array, 
                                                          n_controls);
 
        if ( get_debug_level() >= 5 ) {
            fprintf(stderr,"Control ($%p) %d  -->  Control ($%p) %d\n",
                    cont, i, succ, j);
        }
 
        /* Here, we give equal possibility , 1 for each one */
        ACCESS(P, n_controls, i, j) = VALUE_ONE;
        if (!already_examined[j])
            node_successors_to_matrix(succ, P, n_controls,
                                      control_array, already_examined);
        else {
            if ( get_debug_level() >= 5 ) {
                fprintf(stderr, "Control Number %d already examined!\n",j);
            }
        }
    }, control_successors(cont));
}

References ACCESS, CAR, CONTROL, control_element_position_in_control_array(), control_successors, fprintf(), get_bool_property(), get_debug_level(), MAPL, and VALUE_ONE.

Referenced by average_probability_matrix().

Here is the call graph for this function:

Here is the caller graph for this function:

unstructured_to_complexity()

complexity unstructured_to_complexity	(	unstructured	unstr,
		transformer	precond,
		list	effects_list
	)

6th element of instruction

comp_unstr.c

complexity unstructured_to_complexity(unstructured unstr; transformer precond; list effects_list;

Return the complexity of the unstructured graph unstr whose nodes are controls.

First runs through the graph to compute nodes' complexities, the total number of nodes, and give a number to each node. This is done in "controls_to_hash_table()".

Then runs again through it to fill the probability matrix [Pij] ( Pij = probability to go to node j when you're in node i) This is done in "build_probability_matrix()"

Then computes A = I-P, then inv_A = 1/A with the matrix package.

MAX_CONTROLS_IN_UNSTRUCTURED = 100

A is identity matrix I

B = A - P = I - P

matrice_general_inversion(B, A, n_controls);

A = 1/(B)

This region will call C routines. LZ 20/10/92

the "global" complexity is: comp = a11 * C1 + a12 * C2 + ... + a1n * Cn where Ci = complexity of control #i

Modif by AP, March 15th 93: old version had non constant int in dim decl float fa[n_controls][n_controls]; int indx[n_controls]; int d;

Parameters

unstr	nstr
precond	recond
effects_list	ffects_list

Definition at line 75 of file comp_unstr.c.

{
    complexity comp = make_zero_complexity(); 
    hash_table hash_control_to_complexity = hash_table_make(hash_pointer, 
                                            MAX_CONTROLS_IN_UNSTRUCTURED);
    int i, j, n_controls = 0;
    control control_array[MAX_CONTROLS_IN_UNSTRUCTURED];
    matrice P, A, B;
 
    trace_on("unstructured");
 
    controls_to_hash_table(unstructured_control(unstr),
                           &n_controls,
                           control_array,
                           hash_control_to_complexity,
                           precond,
                           effects_list);
    
     
    P = average_probability_matrix(unstr, n_controls, control_array);
    A = matrice_new(n_controls, n_controls);
    B = matrice_new(n_controls, n_controls);
 
    /* A is identity matrix I */
    matrice_identite(A, n_controls, 0);   
    /* B = A - P =  I - P */
    matrice_substract(B, A, P, n_controls, n_controls);  
 
    if (get_debug_level() >= 5) {
        fprintf(stderr, "I - P =");
        matrice_fprint(stderr, B, n_controls, n_controls);
    }
 
    /* matrice_general_inversion(B, A, n_controls);  */    
    /* A = 1/(B) */
    /* This region will call C routines. LZ 20/10/92  */
 
    /* 
       the "global" complexity is:
       comp = a11 * C1 + a12 * C2 + ... + a1n * Cn
       where Ci = complexity of control #i
     */
 
    if ( n_controls < MAX_CONTROLS_IN_UNSTRUCTURED ) {
 
        /* Modif by AP, March 15th 93: old version had non constant int in dim decl
        float fa[n_controls][n_controls];
        int indx[n_controls];
        int d;
        */
        float *fa = (float *) malloc(n_controls*n_controls*sizeof(float));
        int *indx = (int *) malloc(sizeof(int) * n_controls);
        int d;
 
        for (i=1; i<=n_controls; i++) {
            for (j=1; j<=n_controls; j++ ) {
                Value n = ACCESS(B, n_controls, i, j),
                      de = DENOMINATOR(B);
                float f1 = VALUE_TO_FLOAT(n),
                      f2 = VALUE_TO_FLOAT(de);
                FA(i-1,j-1) = f1/f2;
            }
        }
 
        if ( get_debug_level() >= 5 ) {
            fprintf(stderr, "Before float matrice inversion\n\n");
        }
 
        if ( get_debug_level() >= 9 ) {
            fprintf(stderr, "(I - P) =\n");
            for (i=0;i<n_controls;i++) {
                for (j=0;j<n_controls;j++)
                   fprintf(stderr, "%4.2f ",FA(i,j) );
                fprintf(stderr, "\n");
            }
        }
 
        float_matrice_inversion(fa, n_controls, indx, &d);
 
        if ( get_debug_level() >= 5 ) {
            fprintf(stderr, "After  float matrice inversion\n\n");
        }
 
        if ( get_debug_level() >= 9 ) {
            fprintf(stderr, "(I - P)^(-1) =\n");
            for (i=0;i<n_controls;i++) {
                for (j=0;j<n_controls;j++)
                   fprintf(stderr, "%4.2f ",FA(i,j) );
                fprintf(stderr, "\n");
            }
        }
 
        for (i=1; i<=n_controls; i++) {
            control conti = control_array[i];
            complexity compi = (complexity) 
                hash_get(hash_control_to_complexity, (char *) conti);
            float f = FA(0,i-1);
 
            if ( get_debug_level() >= 5 ) {
                fprintf(stderr, "control $%p:f=%f, compl.=", conti, f);
                complexity_fprint(stderr, compi, true, false);
            }
 
            complexity_scalar_mult(&compi, f);
            complexity_add(&comp, compi);
        }
    }
    else
        pips_internal_error("Too large to compute");
 
    if (get_debug_level() >= 5) {
        fprintf(stderr, "cumulated complexity=");
        complexity_fprint(stderr, comp, true, false);
    }
 
    matrice_free(B);
    matrice_free(A);
    matrice_free(P);
 
    hash_table_free(hash_control_to_complexity);
 
    complexity_check_and_warn("unstructured_to_complexity", comp);    
 
    trace_off();
    return(comp);
}

References A, ACCESS, average_probability_matrix(), B, complexity_add(), complexity_check_and_warn(), complexity_fprint(), complexity_scalar_mult(), controls_to_hash_table(), DENOMINATOR, f(), f2(), FA, float_matrice_inversion(), fprintf(), get_debug_level(), hash_get(), hash_pointer, hash_table_free(), hash_table_make(), make_zero_complexity(), malloc(), matrice_fprint(), matrice_free, matrice_identite(), matrice_new, matrice_substract(), MAX_CONTROLS_IN_UNSTRUCTURED, pips_internal_error, trace_off(), trace_on(), unstructured_control, and VALUE_TO_FLOAT.

Referenced by instruction_to_complexity().

Here is the call graph for this function:

Here is the caller graph for this function:

Variable Documentation

hash_callee_to_complexity

hash_table hash_callee_to_complexity

extern

comp_expr_to_pnome.c

scan a ri expression and try to make a polynomial of it Modif: – entity_local_name is replaced by module_local_name. LZ 230993 – MAXINT replaced by INT_MAX, -MAXINT by INT_MIN FI 1/12/95 useful, pips_error is defined there

Definition at line 57 of file comp_scan.c.

hash_complexity_parameters

hash_table hash_complexity_parameters

extern

Definition at line 58 of file comp_scan.c.