comp_unstr.c

Go to the documentation of this file.

/*
 
  $Id: comp_unstr.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
/* comp_unstr.c */
/* evaluate the complexity of unstructured graphs of statements */
 
#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"  /* used by get_bool_property   */
#include "misc.h"
#include "matrice.h"
#include "complexity.h"
 
/* Added by AP, March 15th 93: allows the simulation of a two-dimensional array
 * with a mono-dimensional memory allocation.
 */
#define FA(i,j) fa[(i)*n_controls + (j)]
 
extern hash_table hash_callee_to_complexity;
extern hash_table hash_complexity_parameters;
 
/* 6th element of instruction */
/* 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
 */
complexity unstructured_to_complexity(unstr, precond, effects_list)
unstructured unstr;
transformer precond;
list effects_list;
{
    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);
}
 
␌
/* 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
 */
void controls_to_hash_table(cont, pn_controls, control_array,
                            hash_control_to_complexity, precond, effects_list)
control cont;
int *pn_controls;
control control_array[];
hash_table hash_control_to_complexity;
transformer precond;
list effects_list;
{
    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));
}
 
/* return the number i, that is i'th element of the control array
 * Note that i begins from 1 instead of 0 
 */
int control_element_position_in_control_array(cont, control_array, n_controls)
control cont;
control control_array[];
int n_controls;
{
    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);
}
 
 
matrice average_probability_matrix(unstr, n_controls, control_array)
unstructured unstr;
int n_controls;
control control_array[];
{
    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);
}
 
/* 
 * 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
 */
void node_successors_to_matrix(cont, P, n_controls,
                               control_array, already_examined)
control cont;
matrice P;
int n_controls;
control control_array[];
bool already_examined[];
{
    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));
}