PIPS
|
#include <stdlib.h>
#include <stdio.h>
#include <limits.h>
#include <string.h>
#include "linear.h"
#include "genC.h"
#include "ri.h"
#include "effects.h"
#include "complexity_ri.h"
#include "ri-util.h"
#include "pipsdbm.h"
#include "workspace-util.h"
#include "effects-util.h"
#include "misc.h"
#include "properties.h"
#include "complexity.h"
Go to the source code of this file.
Macros | |
#define | maxint_p(i) ((i) == INT_MAX) |
#define | minint_p(i) ((i) == (INT_MIN)) |
Functions | |
char * | noms_var (entity e) |
comp_expr_to_pnome.c More... | |
complexity | make_complexity_unknown (const char *name) |
builds a new unknown complexity attached to a virtual package More... | |
complexity | expression_to_complexity_polynome (expression expr, transformer precond, list effects_list, bool keep_symbols, int maximize) |
Entry point routine of this file: More... | |
complexity | syntax_to_polynome (syntax synt, transformer precond, list effects_list, bool keep_symbols, int maximize) |
1st element of expression More... | |
complexity | normalized_to_polynome (normalized no, transformer precond, list effects_list, bool keep_symbols, int maximize) |
2nd element of expression More... | |
complexity | pvecteur_to_polynome (Pvecteur pvect, transformer precond, list effects_list, bool keep_symbols, int maximize) |
The only element available of normalized. More... | |
complexity | reference_to_polynome (reference ref, transformer precond, list effects_list, bool keep_symbols, int maximize) |
First element of the "syntax" domain. More... | |
complexity | range_to_polynome (range rg __attribute__((__unused__)), transformer precond __attribute__((__unused__)), list effects_list __attribute__((__unused__)), bool keep_symbols __attribute__((__unused__)), int maximize __attribute__((__unused__))) |
2nd element of syntax More... | |
complexity | call_to_polynome (call call_instr, transformer precond, list effects_list, bool keep_symbols, int maximize) |
3rd element of syntax More... | |
complexity | cast_to_polynome (cast cast_instr, transformer precond, list effects_list, bool keep_symbols, int maximize) |
4th element of syntax : Molka Becher More... | |
complexity | plus_op_handler (list args, transformer precond, list effects_list, bool keep_symbols, int maximize) |
complexity | minus_op_handler (list args, transformer precond, list effects_list, bool keep_symbols, int maximize) |
complexity | multiply_op_handler (list args, transformer precond, list effects_list, bool keep_symbols, int maximize) |
complexity | field_op_handler (list args, transformer precond, list effects_list, bool keep_symbols, int maximize) |
complexity | unary_minus_op_handler (list args, transformer precond, list effects_list, bool keep_symbols, int maximize) |
complexity | unary_plus_op_handler (list args, transformer precond, list effects_list, bool keep_symbols, int maximize) |
complexity | divide_op_handler (list args, transformer precond, list effects_list, bool keep_symbols, int maximize) |
complexity | power_op_handler (list args, transformer precond, list effects_list, bool keep_symbols, int maximize) |
complexity | evaluate_var_to_complexity (entity var, transformer precond, list effects_list __attribute__((__unused__)), int maximize) |
complexity evaluate_var_to_complexity(entity var, transformer precond, list effects_list, int maximize) Return, packed in a complexity, the exact value of variable var or its max if (maximize==MAXIMUM_VALUE), or its min, according to preconditions passed in precond. More... | |
complexity | simplify_sc_to_complexity (Psysteme ps, Variable var) |
This function is recently added by L.Zhou June 5, 91 simplify_sc_to_complexity(Psysteme ps, Variable var) It looks for the egality formula containing (Variable)var in the system (Psysteme)ps. More... | |
Variables | |
hash_table | hash_callee_to_complexity |
comp_expr_to_pnome.c More... | |
hash_table | hash_complexity_parameters |
#define maxint_p | ( | i | ) | ((i) == INT_MAX) |
#define minint_p | ( | i | ) | ((i) == (INT_MIN)) |
complexity call_to_polynome | ( | call | call_instr, |
transformer | precond, | ||
list | effects_list, | ||
bool | keep_symbols, | ||
int | maximize | ||
) |
3rd element of syntax
For the moment, we don't want to evaluate the complexity of the
function defined by the users
call_instr | all_instr |
precond | recond |
effects_list | ffects_list |
keep_symbols | eep_symbols |
maximize | aximize |
Definition at line 369 of file comp_expr_to_pnome.c.
References call_arguments, call_function, complexity_float_add(), complexity_fprint(), constant_entity_to_float(), divide_op_handler(), DIVIDE_OPERATOR_NAME, entity_initial, entity_type, f(), field_op_handler(), FIELD_OPERATOR_NAME, fprintf(), get_bool_property(), is_value_code, is_value_constant, is_value_intrinsic, make_zero_complexity(), minus_op_handler(), MINUS_OPERATOR_NAME, module_local_name(), multiply_op_handler(), MULTIPLY_OPERATOR_NAME, pips_internal_error, pips_user_warning, plus_op_handler(), PLUS_OPERATOR_NAME, power_op_handler(), POWER_OPERATOR_NAME, same_string_p, trace_off(), trace_on(), type_functional_p, type_tag, unary_minus_op_handler(), UNARY_MINUS_OPERATOR_NAME, value_code_p, value_constant_p, value_intrinsic_p, and value_tag.
Referenced by syntax_to_polynome().
complexity cast_to_polynome | ( | cast | cast_instr, |
transformer | precond, | ||
list | effects_list, | ||
bool | keep_symbols, | ||
int | maximize | ||
) |
4th element of syntax : Molka Becher
cast_instr | ast_instr |
precond | recond |
effects_list | ffects_list |
keep_symbols | eep_symbols |
maximize | aximize |
Definition at line 429 of file comp_expr_to_pnome.c.
References cast_expression, complexity_fprint(), exp, expression_to_complexity_polynome(), fprintf(), get_bool_property(), trace_off(), and trace_on().
Referenced by syntax_to_polynome().
complexity divide_op_handler | ( | list | args, |
transformer | precond, | ||
list | effects_list, | ||
bool | keep_symbols, | ||
int | maximize | ||
) |
args | rgs |
precond | recond |
effects_list | ffects_list |
keep_symbols | eep_symbols |
maximize | aximize |
Definition at line 560 of file comp_expr_to_pnome.c.
References CAR, CDR, complexity_constant_p(), complexity_mult(), complexity_rm(), complexity_TCST(), DONT_KEEP_SYMBOLS, EXPRESSION, expression_to_complexity_polynome(), make_constant_complexity(), and user_error.
Referenced by call_to_polynome().
complexity evaluate_var_to_complexity | ( | entity | var, |
transformer | precond, | ||
list effects_list | __attribute__(__unused__), | ||
int | maximize | ||
) |
complexity evaluate_var_to_complexity(entity var, transformer precond, list effects_list, int maximize) Return, packed in a complexity, the exact value of variable var or its max if (maximize==MAXIMUM_VALUE), or its min, according to preconditions passed in precond.
If nothing is found, the complexity returned is UNKNOWN_VARIABLE, with a varcount_unknown set to 1. The variable statistics are up to date in the new complexity returned, in any case.
FI: I do not understand this algorithm as it does not try the easiest substitution, using any equation in precond that uses var with a non-zero coefficient.
This is the only case that we use the precondition
added by LZ 18/02/92
for the inner loop 28/06/91 example p.f
Definition at line 643 of file comp_expr_to_pnome.c.
References Ssysteme::base, complexity_varcount, complexity_zero_p(), Ssysteme::egalites, entity_integer_scalar_p(), entity_name, fprint_string_Value(), fprint_Value(), fprintf(), get_bool_property(), hash_complexity_parameters, hash_contains_p, hash_contains_user_var_p, make_constant_complexity(), make_single_var_complexity(), make_zero_complexity(), max, min, module_local_name(), noms_var(), precondition_to_string(), predicate_system, predicate_undefined, sc_dup(), sc_fprint(), sc_minmax_of_variable(), simplify_sc_to_complexity(), Svecteur::succ, TAKE_MAX, TAKE_MIN, trace_off(), trace_on(), transformer_relation, transformer_undefined, val_of, VALUE_MAX, value_max_p, VALUE_MIN, value_min_p, value_notmax_p, value_notmin_p, VALUE_TO_FLOAT, var_of, varcount_bounded, varcount_guessed, varcount_unknown, and VECTEUR_NUL_P.
Referenced by block_to_complexity(), final_statement_to_complexity_evaluation(), new_block_to_complexity(), pvecteur_to_polynome(), and reference_to_polynome().
complexity expression_to_complexity_polynome | ( | expression | expr, |
transformer | precond, | ||
list | effects_list, | ||
bool | keep_symbols, | ||
int | maximize | ||
) |
Entry point routine of this file:
complexity expression_to_complexity_polynome(expression expr, transformer precond, list effects_list, bool keep_symbols, int maximize) return the polynomial associated to the expression expr, or POLYNOME_UNDEFINED if it's not a polynome. or POLYNOME_NULL if it's a 0 complexity. If keep_symbols is false, we force evaluation of variables. If they can't be evaluated, they enter the polynomial, but they are replaced by the pseudo-variable UNKNOWN_VARIABLE, except when they appear in a loop range: in that case, the whole range is replaced by UNKNOWN_RANGE. The int maximize lets us use the mins and maxs of preconditions system, to compute a WORST-CASE complexity for the upper bound , maximize is 1 for the lower bound and increment, maximize is -1 (when the precondition doesn't give an exact value)
effects_list is added on 10 Nov 92 to pass the effects which can be used to determine the "must-be-written" effects to delay the variable evaluation. LZ 10 Nov 92
FI:
The following line is merely for debugging
expr | xpr |
precond | recond |
effects_list | ffects_list |
keep_symbols | eep_symbols |
maximize | aximize |
Definition at line 118 of file comp_expr_to_pnome.c.
References complexity_fprint(), complexity_undefined, complexity_unknown_p(), expression_syntax, expression_undefined, fprintf(), get_bool_property(), make_zero_complexity(), NORMALIZE_EXPRESSION, normalized_linear_p, normalized_to_polynome(), pips_internal_error, syntax_to_polynome(), syntax_undefined, trace_off(), and trace_on().
Referenced by cast_to_polynome(), divide_op_handler(), field_op_handler(), loop_to_complexity(), minus_op_handler(), multiply_op_handler(), plus_op_handler(), power_op_handler(), replace_formal_parameters_by_real_ones(), unary_minus_op_handler(), unary_plus_op_handler(), and whileloop_to_complexity().
complexity field_op_handler | ( | list | args, |
transformer | precond, | ||
list | effects_list, | ||
bool | keep_symbols, | ||
int | maximize | ||
) |
args | rgs |
precond | recond |
effects_list | ffects_list |
keep_symbols | eep_symbols |
maximize | aximize |
Definition at line 512 of file comp_expr_to_pnome.c.
References CAR, CDR, complexity_add(), complexity_rm(), EXPRESSION, and expression_to_complexity_polynome().
Referenced by call_to_polynome().
complexity make_complexity_unknown | ( | const char * | name | ) |
builds a new unknown complexity attached to a virtual package
name | ame |
Definition at line 81 of file comp_expr_to_pnome.c.
References COMPLEXITY_PACKAGE_NAME, DEFAULT_INTEGER_TYPE_SIZE, entity_undefined_p, make_basic_int(), make_empty_program(), make_language_fortran(), make_new_scalar_variable_with_prefix(), make_single_var_complexity(), and package.
Referenced by simplify_sc_to_complexity(), and whileloop_to_complexity().
complexity minus_op_handler | ( | list | args, |
transformer | precond, | ||
list | effects_list, | ||
bool | keep_symbols, | ||
int | maximize | ||
) |
args | rgs |
precond | recond |
effects_list | ffects_list |
keep_symbols | eep_symbols |
maximize | aximize |
Definition at line 472 of file comp_expr_to_pnome.c.
References CAR, CDR, complexity_rm(), complexity_sub(), EXPRESSION, and expression_to_complexity_polynome().
Referenced by call_to_polynome().
complexity multiply_op_handler | ( | list | args, |
transformer | precond, | ||
list | effects_list, | ||
bool | keep_symbols, | ||
int | maximize | ||
) |
args | rgs |
precond | recond |
effects_list | ffects_list |
keep_symbols | eep_symbols |
maximize | aximize |
Definition at line 492 of file comp_expr_to_pnome.c.
References CAR, CDR, complexity_mult(), complexity_rm(), EXPRESSION, and expression_to_complexity_polynome().
Referenced by call_to_polynome().
char* noms_var | ( | entity | e | ) |
Definition at line 60 of file comp_expr_to_pnome.c.
References entity_has_values_p(), external_value_name(), module_local_name(), and TCST.
Referenced by evaluate_var_to_complexity(), plint(), plint_pas(), sc_resol_smith(), simplify_sc_to_complexity(), smith_int(), and sol_finale().
complexity normalized_to_polynome | ( | normalized | no, |
transformer | precond, | ||
list | effects_list, | ||
bool | keep_symbols, | ||
int | maximize | ||
) |
2nd element of expression
no | o |
precond | recond |
effects_list | ffects_list |
keep_symbols | eep_symbols |
maximize | aximize |
Definition at line 211 of file comp_expr_to_pnome.c.
References make_zero_complexity(), normalized_linear, normalized_linear_p, pips_internal_error, pvecteur_to_polynome(), trace_off(), and trace_on().
Referenced by expression_to_complexity_polynome().
complexity plus_op_handler | ( | list | args, |
transformer | precond, | ||
list | effects_list, | ||
bool | keep_symbols, | ||
int | maximize | ||
) |
args | rgs |
precond | recond |
effects_list | ffects_list |
keep_symbols | eep_symbols |
maximize | aximize |
Definition at line 452 of file comp_expr_to_pnome.c.
References CAR, CDR, complexity_add(), complexity_rm(), EXPRESSION, and expression_to_complexity_polynome().
Referenced by call_to_polynome().
complexity power_op_handler | ( | list | args, |
transformer | precond, | ||
list | effects_list, | ||
bool | keep_symbols, | ||
int | maximize | ||
) |
polynome_rm(&(complexity_eval(c1)));
(Ppolynome) complexity_eval(c1) = pp;
args | rgs |
precond | recond |
effects_list | ffects_list |
keep_symbols | eep_symbols |
maximize | aximize |
Definition at line 589 of file comp_expr_to_pnome.c.
References CAR, CDR, complexity_constant_p(), complexity_eval, complexity_eval_, complexity_polynome(), complexity_rm(), complexity_TCST(), DONT_KEEP_SYMBOLS, EXPRESSION, expression_to_complexity_polynome(), make_zero_complexity(), newgen_Ppolynome, polynome_power_n(), and polynome_rm().
Referenced by call_to_polynome().
complexity pvecteur_to_polynome | ( | Pvecteur | pvect, |
transformer | precond, | ||
list | effects_list, | ||
bool | keep_symbols, | ||
int | maximize | ||
) |
The only element available of normalized.
bool must_be_written = false;
if (we_must_evaluate && must_be_written) {
should be multiplied by "val" here
We keep this symbol (including TCST) in the polynome
pvect | vect |
precond | recond |
effects_list | ffects_list |
keep_symbols | eep_symbols |
maximize | aximize |
Definition at line 234 of file comp_expr_to_pnome.c.
References complexity_add(), complexity_polynome_add(), complexity_scalar_mult(), complexity_varcount, complexity_zero_p(), evaluate_var_to_complexity(), exp, fprintf(), get_bool_property(), hash_complexity_parameters, hash_contains_p, make_polynome(), make_zero_complexity(), module_local_name(), polynome_to_new_complexity(), prc(), Svecteur::succ, TCST, trace_off(), trace_on(), VALUE_ONE, VALUE_TO_FLOAT, varcount_symbolic, variable_name(), vect_coeff(), vect_first_var(), vect_fprint(), and VECTEUR_NUL_P.
Referenced by normalized_to_polynome().
complexity range_to_polynome | ( | range rg | __attribute__(__unused__), |
transformer precond | __attribute__(__unused__), | ||
list effects_list | __attribute__(__unused__), | ||
bool keep_symbols | __attribute__(__unused__), | ||
int maximize | __attribute__(__unused__) | ||
) |
2nd element of syntax
Definition at line 352 of file comp_expr_to_pnome.c.
References make_zero_complexity(), pips_internal_error, trace_off(), and trace_on().
Referenced by syntax_to_polynome().
complexity reference_to_polynome | ( | reference | ref, |
transformer | precond, | ||
list | effects_list, | ||
bool | keep_symbols, | ||
int | maximize | ||
) |
First element of the "syntax" domain.
bool must_be_written;
if it's an array: let us fail
We keep this symbol in the polynome
ref | ef |
precond | recond |
effects_list | ffects_list |
keep_symbols | eep_symbols |
maximize | aximize |
Definition at line 307 of file comp_expr_to_pnome.c.
References complexity_varcount, evaluate_var_to_complexity(), get_bool_property(), hash_complexity_parameters, hash_contains_p, make_polynome(), make_zero_complexity(), module_local_name(), NIL, polynome_rm(), polynome_to_new_complexity(), ref, reference_indices, reference_variable, trace_off(), trace_on(), VALUE_ONE, and varcount_symbolic.
Referenced by syntax_to_polynome().
complexity simplify_sc_to_complexity | ( | Psysteme | ps, |
Variable | var | ||
) |
This function is recently added by L.Zhou June 5, 91 simplify_sc_to_complexity(Psysteme ps, Variable var) It looks for the egality formula containing (Variable)var in the system (Psysteme)ps.
If ps->egalites is NULL, zero complexity is returned. The rest of the variable in that formula should be the known variable for example: formal parameter(s), inductible variable, etc. EX: M1 - M2 = 1 where M1 is formal parameter where M2 is an inductible variable This function returns M2 = M1 - 1 packed in the polynomial of the complexity the statistics of this complexity should be all zero.
ps | s |
var | ar |
Definition at line 798 of file comp_expr_to_pnome.c.
References complexity_add(), complexity_rm(), complexity_scalar_mult(), complexity_varcount, CONTRAINTE_UNDEFINED_P, get_bool_property(), hash_complexity_parameters, hash_contains_p, make_complexity_unknown(), make_constant_complexity(), make_single_var_complexity(), make_zero_complexity(), module_local_name(), noms_var(), sc_fprint(), Svecteur::succ, TCST, UNKNOWN_VARIABLE_NAME, Svecteur::val, VALUE_ONE, VALUE_TO_FLOAT, value_uminus, Svecteur::var, varcount_unknown, and VECTEUR_NUL_P.
Referenced by evaluate_var_to_complexity().
complexity syntax_to_polynome | ( | syntax | synt, |
transformer | precond, | ||
list | effects_list, | ||
bool | keep_symbols, | ||
int | maximize | ||
) |
1st element of expression
This expression cannot be used within a polynomial, just like an array reference
synt | ynt |
precond | recond |
effects_list | ffects_list |
keep_symbols | eep_symbols |
maximize | aximize |
Definition at line 166 of file comp_expr_to_pnome.c.
References call_to_polynome(), cast_to_polynome(), is_syntax_application, is_syntax_call, is_syntax_cast, is_syntax_range, is_syntax_reference, is_syntax_sizeofexpression, is_syntax_subscript, is_syntax_va_arg, make_zero_complexity(), pips_internal_error, range_to_polynome(), reference_to_polynome(), syntax_call, syntax_cast, syntax_range, syntax_reference, syntax_tag, trace_off(), and trace_on().
Referenced by expression_to_complexity_polynome().
complexity unary_minus_op_handler | ( | list | args, |
transformer | precond, | ||
list | effects_list, | ||
bool | keep_symbols, | ||
int | maximize | ||
) |
args | rgs |
precond | recond |
effects_list | ffects_list |
keep_symbols | eep_symbols |
maximize | aximize |
Definition at line 527 of file comp_expr_to_pnome.c.
References CAR, complexity_rm(), complexity_sub(), EXPRESSION, expression_to_complexity_polynome(), and make_zero_complexity().
Referenced by call_to_polynome().
complexity unary_plus_op_handler | ( | list | args, |
transformer | precond, | ||
list | effects_list, | ||
bool | keep_symbols, | ||
int | maximize | ||
) |
args | rgs |
precond | recond |
effects_list | ffects_list |
keep_symbols | eep_symbols |
maximize | aximize |
Definition at line 545 of file comp_expr_to_pnome.c.
References CAR, EXPRESSION, and expression_to_complexity_polynome().
|
extern |
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.
|
extern |
Definition at line 58 of file comp_scan.c.
Referenced by evaluate_var_to_complexity(), pvecteur_to_polynome(), reference_to_polynome(), and simplify_sc_to_complexity().