PIPS
|
#include <stdio.h>
#include <string.h>
#include "linear.h"
#include "genC.h"
#include "ri.h"
#include "effects.h"
#include "complexity_ri.h"
#include "database.h"
#include "ri-util.h"
#include "effects-util.h"
#include "pipsdbm.h"
#include "resources.h"
#include "properties.h"
#include "text-util.h"
#include "misc.h"
#include "matrice.h"
#include "semantics.h"
#include "effects-simple.h"
#include "effects-generic.h"
#include "transformer.h"
#include "complexity.h"
Go to the source code of this file.
Functions | |
bool | uniform_complexities (const string module_name) |
declares the static variable complexity_map and defines its access functions More... | |
bool | fp_complexities (const string module_name) |
bool | any_complexities (const string module_name) |
bool | summary_complexity (const string module_name) |
complexity | statement_to_complexity (statement stat, transformer precon __attribute__((__unused__)), list eff_list __attribute__((__unused__))) |
starting point of Abstract Syntax Tree More... | |
complexity | instruction_to_complexity (instruction instr, transformer precond, list effects_list) |
The only element available of the statement. More... | |
complexity | block_to_complexity (list block, transformer precond, list effects_list) |
1st element of instruction More... | |
complexity | test_to_complexity (test test_instr, transformer precond, list effects_list) |
2nd element of instruction More... | |
complexity | loop_to_complexity (loop loop_instr, transformer precond, list effects_list) |
3rd element of instruction More... | |
complexity | goto_to_complexity (statement st __attribute__((__unused__)), transformer precond __attribute__((__unused__)), list effects_list __attribute__((__unused__))) |
4th element of instruction More... | |
complexity | whileloop_to_complexity (whileloop while_instr, transformer precond, list effects_list) |
5th element of instruction More... | |
complexity | call_to_complexity (call call_instr, basic *pbasic, transformer precond, list effects_list) |
3rd element of syntax More... | |
complexity | arguments_to_complexity (list exprlist, basic *pbasic, transformer precond, list effects_list) |
2nd element of call More... | |
complexity | expression_to_complexity (expression expr, basic *pbasic, transformer precond, list effects_list) |
2nd element of call –arguments More... | |
complexity | subscript_to_complexity (subscript sub, basic *pbasic, transformer precond, list effects_list) |
complexity | syntax_to_complexity (syntax s, basic *pbasic, transformer precond, list effects_list) |
the only available element of expression More... | |
complexity | reference_to_complexity (reference ref, basic *pbasic, transformer precond, list effects_list) |
1st element of syntax More... | |
complexity | indices_to_complexity (list exprlist, basic *pbasic, transformer precond, list effects_list) |
2nd element of reference More... | |
complexity | range_to_complexity (range rng, transformer precond, list effects_list) |
2nd element of syntax More... | |
Variables | |
hash_table | hash_callee_to_complexity = hash_table_undefined |
comp_expr_to_pnome.c More... | |
hash_table | hash_complexity_parameters = hash_table_undefined |
we may need to print preconditions for debugging purposes
module_name | odule_name |
Definition at line 99 of file comp_scan.c.
References add_common_variables_to_hash_table(), add_formal_parameters_to_hash_table(), db_get_memory_resource(), DB_PUT_MEMORY_RESOURCE, debug_off, debug_on, fetch_callees_complexities(), fetch_complexity_parameters(), fprint_cost_table(), fprintf(), free_callees_complexities(), free_value_mappings(), get_bool_property(), get_complexity_map(), get_current_module_entity(), get_current_module_statement(), hash_callee_to_complexity, hash_complexity_parameters, init_cost_table(), load_cumulated_rw_effects_list(), load_statement_precondition(), MAKE_STATEMENT_MAPPING, module_name(), module_name_to_entity(), module_to_value_mappings(), NIL, remove_common_variables_from_hash_table(), remove_formal_parameters_from_hash_table(), reset_complexity_map(), reset_cumulated_rw_effects(), reset_current_module_entity(), reset_current_module_statement(), reset_precondition_map(), reset_proper_rw_effects(), set_complexity_map(), set_cumulated_rw_effects(), set_current_module_entity(), set_current_module_statement(), set_precondition_map(), set_proper_rw_effects(), statement_to_complexity(), strdup(), trace_off(), trace_on(), and transformer_undefined.
Referenced by fp_complexities(), and uniform_complexities().
complexity arguments_to_complexity | ( | list | exprlist, |
basic * | pbasic, | ||
transformer | precond, | ||
list | effects_list | ||
) |
2nd element of call
arguments_to_complexity Return the sum of the complexities of the list of expressions passed. Return also in *pbasic the basic of the "biggest" argument (int/float/double/...)
exprlist | xprlist |
pbasic | basic |
precond | recond |
effects_list | ffects_list |
Definition at line 804 of file comp_scan.c.
References CAR, complexity_add(), complexity_check_and_warn(), complexity_fprint(), EXPRESSION, expression_to_complexity(), fprintf(), free_basic(), get_bool_property(), is_inferior_basic(), MAKE_INT_BASIC, make_zero_complexity(), MAPL, simple_basic_dup(), trace_off(), and trace_on().
Referenced by call_to_complexity().
complexity block_to_complexity | ( | list | block, |
transformer | precond, | ||
list | effects_list | ||
) |
1st element of instruction
Modification:
block | lock |
precond | recond |
effects_list | ffects_list |
Definition at line 344 of file comp_scan.c.
References CAR, complexity_add(), complexity_check_and_warn(), complexity_consistent_p(), complexity_fprint(), complexity_polynome(), complexity_var_subst(), default_is_inferior_pvarval(), effects_write_variable_p(), evaluate_var_to_complexity(), FOREACH, fprintf(), gen_length(), gen_nthcdr(), get_bool_property(), load_cumulated_rw_effects_list(), load_statement_precondition(), make_zero_complexity(), polynome_used_var(), STATEMENT, statement_to_complexity(), Svecteur::succ, trace_off(), trace_on(), Svecteur::var, vect_dup(), VECTEUR_NUL, and VECTEUR_NUL_P.
Referenced by instruction_to_complexity().
complexity call_to_complexity | ( | call | call_instr, |
basic * | pbasic, | ||
transformer | precond, | ||
list | effects_list | ||
) |
3rd element of syntax
The only case that hash_callee_to_complexity is used
transform formal params into real ones
if not format case
call_instr | all_instr |
pbasic | basic |
precond | recond |
effects_list | ffects_list |
Definition at line 736 of file comp_scan.c.
References arguments_to_complexity(), call_arguments, call_function, complexity_check_and_warn(), complexity_float_add(), complexity_fprint(), COMPLEXITY_NOT_FOUND, entity_basic(), entity_initial, entity_name, entity_type, f(), fprintf(), get_bool_property(), hash_callee_to_complexity, hash_get(), intrinsic_cost(), is_value_code, is_value_constant, is_value_intrinsic, is_value_symbolic, is_value_unknown, make_zero_complexity(), module_local_name(), pips_assert, pips_internal_error, replace_formal_parameters_by_real_ones(), trace_off(), trace_on(), type_functional_p, type_statement_p, type_void_p, user_error, and value_tag.
Referenced by instruction_to_complexity(), and syntax_to_complexity().
complexity expression_to_complexity | ( | expression | expr, |
basic * | pbasic, | ||
transformer | precond, | ||
list | effects_list | ||
) |
2nd element of call –arguments
2nd element of reference –indices
expr | xpr |
pbasic | basic |
precond | recond |
effects_list | ffects_list |
Definition at line 838 of file comp_scan.c.
References complexity_check_and_warn(), expression_syntax, make_zero_complexity(), pips_internal_error, syntax_to_complexity(), syntax_undefined, trace_off(), and trace_on().
Referenced by arguments_to_complexity(), indices_to_complexity(), instruction_to_complexity(), range_to_complexity(), subscript_to_complexity(), syntax_to_complexity(), test_to_complexity(), and whileloop_to_complexity().
module_name | odule_name |
Definition at line 89 of file comp_scan.c.
References any_complexities(), and module_name().
complexity goto_to_complexity | ( | statement st | __attribute__(__unused__), |
transformer precond | __attribute__(__unused__), | ||
list effects_list | __attribute__(__unused__) | ||
) |
4th element of instruction
Definition at line 683 of file comp_scan.c.
References make_zero_complexity(), and pips_internal_error.
Referenced by instruction_to_complexity().
complexity indices_to_complexity | ( | list | exprlist, |
basic * | pbasic, | ||
transformer | precond, | ||
list | effects_list | ||
) |
2nd element of reference
exactly the same with arguments_to_complexity I add this function in order to make the structure clearer Apr. 15,91
exprlist | xprlist |
pbasic | basic |
precond | recond |
effects_list | ffects_list |
Definition at line 1057 of file comp_scan.c.
References CAR, complexity_add(), complexity_check_and_warn(), complexity_rm(), EXPRESSION, expression_to_complexity(), free_basic(), is_inferior_basic(), MAKE_INT_BASIC, make_zero_complexity(), MAPL, simple_basic_dup(), trace_off(), and trace_on().
Referenced by reference_to_complexity(), and subscript_to_complexity().
complexity instruction_to_complexity | ( | instruction | instr, |
transformer | precond, | ||
list | effects_list | ||
) |
The only element available of the statement.
dummy parameter
dummy parameter
instr | nstr |
precond | recond |
effects_list | ffects_list |
Definition at line 275 of file comp_scan.c.
References block_to_complexity(), call_to_complexity(), complexity_check_and_warn(), expression_to_complexity(), goto_to_complexity(), instruction_block, instruction_call, instruction_expression, instruction_goto, instruction_loop, instruction_tag, instruction_test, instruction_unstructured, instruction_whileloop, is_instruction_block, is_instruction_call, is_instruction_expression, is_instruction_goto, is_instruction_loop, is_instruction_test, is_instruction_unstructured, is_instruction_whileloop, loop_to_complexity(), MAKE_INT_BASIC, make_zero_complexity(), pips_internal_error, test_to_complexity(), trace_off(), trace_on(), unstructured_to_complexity(), and whileloop_to_complexity().
Referenced by statement_to_complexity().
complexity loop_to_complexity | ( | loop | loop_instr, |
transformer | precond, | ||
list | effects_list | ||
) |
3rd element of instruction
FI: Lei chose to allocate the UL and UU entities in the current module... Maybe, we are ready fo some dynamic profiling...
string mod_name = entity_module_name(ll);
if the statement were still reachable, we could try to use the statement nunber...
In order to get rid of at-sign, add 1 , LZ 010492
tell callees that they mustn't try to evaluate the loop index
cioh cboh are derived from overhead file "overhead" LZ, 280993
zero iteration for sure
at least one iteration
maybe some iteration
an intermediate test based on preconditions would give better result with affine loop bounds
loop_instr | oop_instr |
precond | recond |
effects_list | ffects_list |
Definition at line 460 of file comp_scan.c.
References AddEntityToCurrentModule(), asprintf, complexity_check_and_warn(), complexity_constant_p(), complexity_degree(), complexity_div(), complexity_fprint(), complexity_is_monomial_p(), complexity_polynome(), complexity_polynome_add(), complexity_rangecount, complexity_rm(), complexity_scalar_mult(), complexity_sigma(), complexity_stats_add(), complexity_TCST(), complexity_unknown_p(), empty_global_label_p(), entity_local_name(), entity_name, execution_parallel_p, expression_to_complexity_polynome(), fprintf(), free(), free_complexity(), get_bool_property(), get_current_module_entity(), hash_complexity_parameters, hash_del(), HASH_LOOP_INDEX, hash_put(), intrinsic_cost(), is_basic_int, KEEP_SYMBOLS, loop_body, LOOP_BRANCH_OVERHEAD, loop_execution, loop_index, LOOP_INIT_OVERHEAD, loop_label, loop_range, make_constant_complexity(), MAKE_INT_BASIC, make_new_scalar_variable_with_prefix(), make_single_var_complexity(), make_zero_complexity(), MakeBasic(), MAXIMUM_VALUE, MINIMUM_VALUE, module_local_name(), range_increment, range_lower, range_to_complexity(), range_upper, rangecount_guessed, statement_to_complexity(), strdup(), trace_off(), trace_on(), user_error, and user_warning.
Referenced by instruction_to_complexity().
complexity range_to_complexity | ( | range | rng, |
transformer | precond, | ||
list | effects_list | ||
) |
2nd element of syntax
rng | ng |
precond | recond |
effects_list | ffects_list |
Definition at line 1089 of file comp_scan.c.
References complexity_add(), complexity_check_and_warn(), complexity_fprint(), complexity_rm(), expression_to_complexity(), expression_undefined_p, fprintf(), get_bool_property(), pips_internal_error, range_increment, range_lower, range_upper, trace_off(), and trace_on().
Referenced by loop_to_complexity(), and syntax_to_complexity().
complexity reference_to_complexity | ( | reference | ref, |
basic * | pbasic, | ||
transformer | precond, | ||
list | effects_list | ||
) |
1st element of syntax
reference_to_complexity: return the complexity of the computing of the indices plus the complexity of one memory read Also return basic type of variable in *pbasic.
indices basic
ci=compindexation, ca=compaccess
ci=compindexation counts multi-dimension arrays indexation costs
ref | ef |
pbasic | basic |
precond | recond |
effects_list | ffects_list |
Definition at line 952 of file comp_scan.c.
References basic_complex_p, basic_derived_p, basic_float_p, basic_int_p, basic_logical_p, basic_pointer_p, basic_string_p, basic_tag, complexity_add(), complexity_check_and_warn(), complexity_fprint(), complexity_rm(), entity_basic_concrete_type(), entity_name, entity_register_p(), FIVE_INDEX_NAME, FOUR_INDEX_NAME, fprintf(), gen_length(), get_bool_property(), indices_to_complexity(), intrinsic_cost(), MAKE_ADDRESS_BASIC, make_constant_complexity(), MAKE_INT_BASIC, MAKE_STRING_BASIC, make_zero_complexity(), MEMORY_READ_NAME, module_local_name(), ONE_INDEX_NAME, ref, reference_indices, reference_variable, SEVEN_INDEX_NAME, simple_basic_dup(), SIX_INDEX_NAME, THREE_INDEX_NAME, trace_off(), trace_on(), TWO_INDEX_NAME, type_variable, user_warning, and variable_basic.
Referenced by syntax_to_complexity().
complexity statement_to_complexity | ( | statement | stat, |
transformer precon | __attribute__(__unused__), | ||
list eff_list | __attribute__(__unused__) | ||
) |
starting point of Abstract Syntax Tree
Check and store the complexity in the statement_mapping
SET_STATEMENT_MAPPING(get_complexity_map() , stat, (char *) comp);
Definition at line 230 of file comp_scan.c.
References complexity_check_and_warn(), complexity_consistent_p(), complexity_fprint(), fprintf(), get_bool_property(), instruction_to_complexity(), instruction_undefined, load_cumulated_rw_effects_list(), load_statement_precondition(), make_zero_complexity(), module_local_name(), ORDERING_NUMBER, ORDERING_STATEMENT, pips_assert, pips_internal_error, statement_instruction, statement_label, statement_ordering, store_statement_complexity(), trace_off(), and trace_on().
Referenced by any_complexities(), block_to_complexity(), controls_to_hash_table(), loop_to_complexity(), new_block_to_complexity(), test_to_complexity(), and whileloop_to_complexity().
complexity subscript_to_complexity | ( | subscript | sub, |
basic * | pbasic, | ||
transformer | precond, | ||
list | effects_list | ||
) |
G:let us assume . cost 1
sub | ub |
pbasic | basic |
precond | recond |
effects_list | ffects_list |
Definition at line 860 of file comp_scan.c.
References complexity_add(), complexity_float_add(), complexity_rm(), expression_to_complexity(), indices_to_complexity(), subscript_array, and subscript_indices.
Referenced by syntax_to_complexity().
summary_comp_dup = complexity_dup(summary_comp);
module_name | odule_name |
Definition at line 179 of file comp_scan.c.
References complexity_consistent_p(), COMPLEXITY_NOT_FOUND, copy_complexity(), db_get_memory_resource(), DB_PUT_MEMORY_RESOURCE, debug_off, debug_on, fprintf(), get_bool_property(), get_current_module_statement(), load_statement_complexity(), make_zero_complexity(), module_name(), pips_assert, pips_internal_error, reset_complexity_map(), reset_current_module_statement(), set_complexity_map(), set_current_module_statement(), strdup(), trace_off(), and trace_on().
complexity syntax_to_complexity | ( | syntax | s, |
basic * | pbasic, | ||
transformer | precond, | ||
list | effects_list | ||
) |
the only available element of expression
A cost for casting could be added, although casting is mostly used for typing issue. However, (float) 2 has a cost.
TypeCast operation added by Molka Becher to complexity_cost_tables for handling the cost of cast when it is necessary, 24 March 2011
Compiler generated constant: equivalent to a constant load --> 0
pbasic | basic |
precond | recond |
effects_list | ffects_list |
Definition at line 881 of file comp_scan.c.
References call_to_complexity(), cast_expression, complexity_add(), complexity_check_and_warn(), complexity_rm(), expression_to_complexity(), intrinsic_cost(), 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_constant_complexity(), MAKE_INT_BASIC, make_zero_complexity(), pips_internal_error, range_to_complexity(), reference_to_complexity(), sizeofexpression_expression, sizeofexpression_expression_p, subscript_to_complexity(), syntax_call, syntax_cast, syntax_range, syntax_reference, syntax_sizeofexpression, syntax_subscript, syntax_tag, trace_off(), trace_on(), and TYPE_CAST_COST.
Referenced by expression_to_complexity().
complexity test_to_complexity | ( | test | test_instr, |
transformer | precond, | ||
list | effects_list | ||
) |
2nd element of instruction
test_instr | est_instr |
precond | recond |
effects_list | ffects_list |
Definition at line 414 of file comp_scan.c.
References complexity_add(), complexity_check_and_warn(), complexity_dup(), complexity_fprint(), complexity_ifcount, complexity_rm(), complexity_scalar_mult(), complexity_zero_p(), expression_to_complexity(), fprintf(), get_bool_property(), ifcount_halfhalf, statement_to_complexity(), test_condition, test_false, test_true, trace_off(), and trace_on().
Referenced by instruction_to_complexity().
declares the static variable complexity_map and defines its access functions
bool complexities(module_name) Entry point called by the pips makefile
"hash_callee_to_complexity" contains a list of summary_complexity of callees, Non-recursive: callees complexities are supposed to be computed when arriving here.
"hash_complexity_parameters" contains the list of variables that we don't want to evaluate; so they will appear in the polynomial. All other variables (except for the loop indices) are evaluated as the scan proceeds, thanks to semantic analysis. Those which can't be evaluated are replaced by the pseudo-variable UNKNOWN_VARIABLE, which will be given an arbitrary value at the end of the evaluation.
module_name | odule_name |
Definition at line 79 of file comp_scan.c.
References any_complexities(), and module_name().
complexity whileloop_to_complexity | ( | whileloop | while_instr, |
transformer | precond, | ||
list | effects_list | ||
) |
5th element of instruction
while_instr | hile_instr |
precond | recond |
effects_list | ffects_list |
Definition at line 692 of file comp_scan.c.
References call_arguments, call_function, CAR, CDR, complexity_add(), complexity_check_and_warn(), complexity_fprint(), complexity_mult(), ENTITY_LESS_THAN_P, exp, EXPRESSION, expression_syntax, expression_to_complexity(), expression_to_complexity_polynome(), fprintf(), get_bool_property(), KEEP_SYMBOLS, make_complexity_unknown(), make_op_exp(), MINIMUM_VALUE, MINUS_OPERATOR_NAME, statement_to_complexity(), syntax_call, UNKNOWN_RANGE_NAME, whileloop_body, and whileloop_condition.
Referenced by instruction_to_complexity().
hash_table hash_callee_to_complexity = hash_table_undefined |
cproto-generated files
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.
Referenced by any_complexities(), and call_to_complexity().
hash_table hash_complexity_parameters = hash_table_undefined |
Definition at line 58 of file comp_scan.c.
Referenced by any_complexities(), evaluate_var_to_complexity(), loop_to_complexity(), pvecteur_to_polynome(), reference_to_polynome(), and simplify_sc_to_complexity().