constraints.c File Reference

#include <ctype.h>
#include "genC.h"
#include "linear.h"
#include "ri.h"
#include "effects.h"
#include "ri-util.h"
#include "workspace-util.h"
#include "effects-util.h"
#include "text.h"
#include "pipsdbm.h"
#include "resources.h"
#include "properties.h"
#include "misc.h"
#include "control.h"
#include "conversion.h"
#include "expressions.h"
#include "effects-generic.h"
#include "effects-simple.h"
#include "effects-convex.h"
#include "text-util.h"
#include "parser_private.h"
#include "semantics.h"
#include "transformer.h"
#include "accel-util.h"

Include dependency graph for constraints.c:

Go to the source code of this file.

Functions
static bool	do_solve_hardware_constraints_on_nb_proc (entity e, statement s)
static bool	do_solve_hardware_constraints_on_volume (entity unknown, statement s)
static bool	do_solve_hardware_constraints (statement s)
	the equation is given by sum(e) { | REGION_READ(e) U REGION_WRITE(e) | } < VOLUME More...
bool	solve_hardware_constraints (const char *module_name)
	constraints.c More...

Function Documentation

do_solve_hardware_constraints()

static bool do_solve_hardware_constraints ( statement  s )

static

the equation is given by sum(e) { | REGION_READ(e) U REGION_WRITE(e) | } < VOLUME

retreive the unknown variable {

}

Definition at line 248 of file constraints.c.

{
 
    /* retreive the unknown variable { */
    entity unknown = string_to_entity(get_string_property("SOLVE_HARDWARE_CONSTRAINTS_UNKNOWN"),get_current_module_entity());
    if(entity_undefined_p(unknown))
        pips_user_error("must provide the unknown value\n");
    /* } */
    const char* constraint_type = get_string_property("SOLVE_HARDWARE_CONSTRAINTS_TYPE");
    if(same_string_p(constraint_type, "VOLUME"))
        return do_solve_hardware_constraints_on_volume(unknown,s);
    else if(same_string_p(constraint_type, "NB_PROC"))
        return do_solve_hardware_constraints_on_nb_proc(unknown,s);
    else {
        pips_user_error("constraint type '%s' unknown\n",constraint_type);
        return false;
    }
}

References do_solve_hardware_constraints_on_nb_proc(), do_solve_hardware_constraints_on_volume(), entity_undefined_p, get_current_module_entity(), get_string_property(), pips_user_error, same_string_p, and string_to_entity().

Referenced by solve_hardware_constraints().

Here is the call graph for this function:

Here is the caller graph for this function:

do_solve_hardware_constraints_on_nb_proc()

static bool do_solve_hardware_constraints_on_nb_proc ( entity  e, statement  s  )

static

add a new constraint to the system

check we have not already dealt with this variable

get the associated read and write regions

compute their convex hull

solve the equation if it is linear

create a system with preconditions information and the constraint limit

find numerical constraints over unknown e

SG: this is over optimistic, we should verify all elements of soluce are store-independant

welcome in the real life (RK(C) we cannot solve this equation at commile time ... never mind let's do it at runtime !

Definition at line 58 of file constraints.c.

                                                                            {
    list regions = load_cumulated_rw_effects_list(s);
 
    list read_regions = regions_read_regions(regions);
    list write_regions = regions_write_regions(regions);
    transformer tr = transformer_range(load_statement_precondition(s));
    /* add a new constraint to the system */
    Pvecteur pv = vect_new(e,-1);
    vect_add_elem(&pv,TCST,3);
    sc_add_inegalite(predicate_system(transformer_relation(tr)),
            contrainte_make(pv));
 
    set visited_entities = set_make(set_pointer);
 
    expression max_dim = expression_undefined;
    FOREACH(REGION,reg,regions)
    {
        reference r = region_any_reference(reg);
        entity e = reference_variable(r);
        /* check we have not already dealt with this variable */
        if(!set_belong_p(visited_entities,e))
        {
            set_add_element(visited_entities,visited_entities,e);
            if(entity_array_p(e)) {
                /* get the associated read and write regions */
                region read_region = find_region_on_entity(e,read_regions);
                region write_region = find_region_on_entity(e,write_regions);
                /* compute their convex hull */
                region rw_region = 
                    region_undefined_p(read_region)?write_region:
                    region_undefined_p(write_region)?read_region:
                    regions_must_convex_hull(read_region,write_region);
 
                region hregion = rw_region;//region_hypercube(rw_region);
                entity phi = expression_to_entity(EXPRESSION(CAR(reference_indices(r))));
                list ephis = expressions_to_entities(reference_indices(r));
                Pbase phis = list_to_base(ephis);
                gen_free_list(ephis);
                Psysteme hsc = sc_rectangular_hull(region_system(hregion),phis);
                base_rm(phis);
 
                Pcontrainte lower,upper;
                constraints_for_bounds(phi,&sc_inegalites(hsc),&lower,&upper);
                if(!CONTRAINTE_UNDEFINED_P(lower) && !CONTRAINTE_UNDEFINED_P(upper))
                {
                    expression elower = constraints_to_loop_bound(lower,phi,true,entity_intrinsic(DIVIDE_OPERATOR_NAME));
                    simplify_minmax_expression(elower,tr);
                    expression eupper = constraints_to_loop_bound(upper,phi,false,entity_intrinsic(DIVIDE_OPERATOR_NAME));
                    simplify_minmax_expression(eupper,tr);
                    expression dist = make_op_exp(MINUS_OPERATOR_NAME,eupper,elower);
                    dist=make_op_exp(PLUS_OPERATOR_NAME,dist,int_to_expression(1));
 
                    if(expression_undefined_p(max_dim))
                        max_dim = dist;
                    else {
                        max_dim = MakeBinaryCall(
                                entity_intrinsic(MAX_OPERATOR_NAME),
                                max_dim,
                                dist
                                );
                        simplify_minmax_expression(max_dim,tr);
                    }
 
                }
                else
                    pips_user_error("failed to gather enough information for entity %s\n",entity_user_name(e));
            }
        }
    }
    int max_volume= get_int_property("SOLVE_HARDWARE_CONSTRAINTS_LIMIT");
    if(max_volume<=0) pips_user_error("constraint limit must be greater than 0\n");
    /* solve the equation if it is linear */
    max_dim=make_op_exp(MINUS_OPERATOR_NAME,max_dim,int_to_expression(max_volume));
    NORMALIZE_EXPRESSION(max_dim);
    normalized n = expression_normalized(max_dim);
    if(normalized_linear_p(n)) {
        /* create a system with preconditions information and the constraint limit*/
        Psysteme sc = sc_dup(predicate_system(transformer_relation(tr)));
        sc_add_egalite(sc,contrainte_make(normalized_linear(n)));
        /* find numerical constraints over unknown e */
        Value min,max;
        if(sc_minmax_of_variable(sc,e,&min,&max)) {
            expression soluce = Value_to_expression(min);
            /* SG: this is over optimistic, 
             * we should verify all elements of soluce are store-independant
             */
            free_value(entity_initial(e));
            entity_initial(e)=make_value_expression(
                    soluce);
        }
        else /* welcome in the real life (RK(C) we cannot solve this equation at commile time ... never mind let's do it at runtime ! */
            pips_user_error("unable to solve the equation at compile time\n");
    }
    else pips_user_error("unable to get a linear expression for nbproc\n");
 
    set_free(visited_entities);
    gen_free_list(read_regions);
    gen_free_list(write_regions);
    free_transformer(tr);
    return true;
}

References base_rm, CAR, constraints_for_bounds(), constraints_to_loop_bound(), contrainte_make(), CONTRAINTE_UNDEFINED_P, DIVIDE_OPERATOR_NAME, entity_array_p(), entity_initial, entity_intrinsic(), entity_user_name(), EXPRESSION, expression_normalized, expression_to_entity(), expression_undefined, expression_undefined_p, expressions_to_entities(), find_region_on_entity(), FOREACH, free_transformer(), free_value(), gen_free_list(), get_int_property(), int_to_expression(), list_to_base(), load_cumulated_rw_effects_list(), load_statement_precondition(), make_op_exp(), make_value_expression(), MakeBinaryCall(), max, MAX_OPERATOR_NAME, min, MINUS_OPERATOR_NAME, NORMALIZE_EXPRESSION, normalized_linear, normalized_linear_p, pips_user_error, PLUS_OPERATOR_NAME, predicate_system, reference_indices, reference_variable, region, REGION, region_any_reference, region_system, region_undefined_p, regions_must_convex_hull(), regions_read_regions(), regions_write_regions(), sc_add_egalite(), sc_add_inegalite(), sc_dup(), sc_minmax_of_variable(), sc_rectangular_hull(), set_add_element(), set_belong_p(), set_free(), set_make(), set_pointer, simplify_minmax_expression(), TCST, transformer_range(), transformer_relation, Value_to_expression(), vect_add_elem(), and vect_new().

Referenced by do_solve_hardware_constraints().

Here is the call graph for this function:

Here is the caller graph for this function:

do_solve_hardware_constraints_on_volume()

static bool do_solve_hardware_constraints_on_volume ( entity  unknown, statement  s  )

static

check we have not already dealt with this variable

get the associated read and write regions

compute their convex hull

create a string representation of all polynomials gathered

try to solve the polynomial

this takes the floor of the floating point expression ...

insert solution ~ this is an approximation ! it only works if root is increasing

tidy

Definition at line 160 of file constraints.c.

                                                                                 {
    list regions = load_cumulated_rw_effects_list(s);
 
    list read_regions = regions_read_regions(regions);
    list write_regions = regions_write_regions(regions);
    transformer tr = transformer_range(load_statement_precondition(s));
 
    set visited_entities = set_make(set_pointer);
 
    Ppolynome volume_used = POLYNOME_NUL;
    FOREACH(REGION,reg,regions)
    {
        reference r = region_any_reference(reg);
        entity e = reference_variable(r);
        /* check we have not already dealt with this variable */
        if(!set_belong_p(visited_entities,e))
        {
            set_add_element(visited_entities,visited_entities,e);
            if(entity_array_p(e)) {
                /* get the associated read and write regions */
                region read_region = find_region_on_entity(e,read_regions);
                region write_region = find_region_on_entity(e,write_regions);
                /* compute their convex hull */
                region rw_region = 
                    region_undefined_p(read_region)?write_region:
                    region_undefined_p(write_region)?read_region:
                    regions_must_convex_hull(read_region,write_region);
 
                region hregion = rw_region;//region_hypercube(rw_region);
                Ppolynome p = region_enumerate(hregion);
                if(!POLYNOME_UNDEFINED_P(p)) {
                    polynome_add(&volume_used,p);
                    polynome_rm(&p);
                }
                else
                    pips_user_error("unable to compute volume of the region of %s\n",entity_user_name(e));
            }
        }
    }
    int max_volume= get_int_property("SOLVE_HARDWARE_CONSTRAINTS_LIMIT");
    if(max_volume<=0) pips_user_error("constraint limit must be greater than 0\n");
    /* create a string representation of all polynomials gathered */
    Pmonome m = monome_constant_new(-max_volume);
    polynome_monome_add(&volume_used,m);
    monome_rm(&m);
    /* try to solve the polynomial */
    Pvecteur roots = polynome_roots(volume_used,unknown);
    expression eroot = expression_undefined;
    if(VECTEUR_UNDEFINED_P(roots)) { // that is volume_used is independent of unknown
        expression cst = polynome_to_expression(volume_used);
        partial_eval_expression_and_regenerate(&cst,predicate_system(transformer_relation(tr)),load_cumulated_rw_effects(s));
        intptr_t val;
        if(expression_integer_value(cst,&val) && val < 0 )
            eroot=int_to_expression(42);//any value is ok
        else
          // no return
          pips_user_error("no solution possible for this limit\n");
    }
    else {
        Ppolynome root = (Ppolynome)vecteur_var(roots);//yes take the first without thinking more ...
        eroot = polynome_to_expression(root);
        if(expression_constant_p(eroot) &&!expression_integer_constant_p(eroot)) {
            /* this takes the floor of the floating point expression ...*/
            int ival = (int)expression_to_float(eroot);
            free_expression(eroot);
            eroot=int_to_expression(ival);
        }
    }
 
    /* insert solution ~ this is an approximation ! 
     * it only works if root is increasing
     */
    insert_statement(get_current_module_statement(),
            make_assign_statement(entity_to_expression(unknown),eroot),
            true);
 
    /* tidy */
    for(Pvecteur v = roots;!VECTEUR_NUL_P(v);v=vecteur_succ(v))
        polynome_rm((Ppolynome*)&vecteur_var(v));
    vect_rm(roots);
    set_free(visited_entities);
    gen_free_list(read_regions);
    gen_free_list(write_regions);
    free_transformer(tr);
    return true;
}

References entity_array_p(), entity_to_expression(), entity_user_name(), expression_constant_p(), expression_integer_constant_p(), expression_integer_value(), expression_to_float(), expression_undefined, find_region_on_entity(), FOREACH, free_expression(), free_transformer(), gen_free_list(), get_current_module_statement(), get_int_property(), insert_statement(), int, int_to_expression(), intptr_t, load_cumulated_rw_effects(), load_cumulated_rw_effects_list(), load_statement_precondition(), make_assign_statement(), monome_constant_new, monome_rm(), partial_eval_expression_and_regenerate(), pips_user_error, polynome_add(), polynome_monome_add(), POLYNOME_NUL, polynome_rm(), polynome_roots(), polynome_to_expression(), POLYNOME_UNDEFINED_P, predicate_system, reference_variable, region, REGION, region_any_reference, region_enumerate(), region_undefined_p, regions_must_convex_hull(), regions_read_regions(), regions_write_regions(), set_add_element(), set_belong_p(), set_free(), set_make(), set_pointer, transformer_range(), transformer_relation, vect_rm(), VECTEUR_NUL_P, vecteur_succ, VECTEUR_UNDEFINED_P, and vecteur_var.

Referenced by do_solve_hardware_constraints().

Here is the call graph for this function:

Here is the caller graph for this function:

solve_hardware_constraints()

bool solve_hardware_constraints

(

const char *

module_name

)

constraints.c

validate

Parameters

module_name

odule_name

Definition at line 267 of file constraints.c.

{
    debug_on("SOLVE_HARDWARE_CONSTRAINTS");
    set_current_module_entity(module_name_to_entity( module_name ));
    set_current_module_statement((statement) db_get_memory_resource(DBR_CODE, module_name, true) );
    set_cumulated_rw_effects((statement_effects)db_get_memory_resource(DBR_REGIONS, module_name, true));
    set_proper_rw_effects((statement_effects)db_get_memory_resource(DBR_PROPER_EFFECTS, module_name, true));
    module_to_value_mappings(get_current_module_entity());
    set_precondition_map( (statement_mapping) db_get_memory_resource(DBR_PRECONDITIONS, module_name, true) );
 
    const char* stmt_label=get_string_property("SOLVE_HARDWARE_CONSTRAINTS_LABEL");
    statement equation_to_solve = find_statement_from_label_name(get_current_module_statement(),get_current_module_name(),stmt_label);
 
    bool result =false;
    if(!statement_undefined_p(equation_to_solve))
    {
        if((result=do_solve_hardware_constraints(equation_to_solve))) {
            /* validate */
            module_reorder(get_current_module_statement());
            DB_PUT_MEMORY_RESOURCE(DBR_CODE, module_name,get_current_module_statement());
        }
    }
 
    reset_current_module_entity();
    reset_current_module_statement();
    reset_cumulated_rw_effects();
    reset_proper_rw_effects();
    reset_precondition_map();
    free_value_mappings();
    debug_off();
    return result;
}

References db_get_memory_resource(), DB_PUT_MEMORY_RESOURCE, debug_off, debug_on, do_solve_hardware_constraints(), find_statement_from_label_name(), free_value_mappings(), get_current_module_entity(), get_current_module_name(), get_current_module_statement(), get_string_property(), module_name(), module_name_to_entity(), module_reorder(), module_to_value_mappings(), reset_cumulated_rw_effects(), reset_current_module_entity(), reset_current_module_statement(), reset_precondition_map(), reset_proper_rw_effects(), set_cumulated_rw_effects(), set_current_module_entity(), set_current_module_statement(), set_precondition_map(), set_proper_rw_effects(), and statement_undefined_p.

Here is the call graph for this function: