26 #if defined(BUILDER_SIMPLIFY_CONTROL) || \
27 defined(BUILDER_SIMPLIFY_CONTROL_DIRECTLY) || \
28 defined(BUILDER_SUPPRESS_DEAD_CODE) || \
29 defined(BUILDER_REMOVE_USELESS_LABEL)
32 #include "pips_config.h"
67 static bool some_unstructured_ifs_have_been_changed;
71 static int dead_code_if_removed;
72 static int dead_code_if_replaced_by_its_effect;
73 static int dead_code_if_false_branch_removed;
74 static int dead_code_if_true_branch_removed;
75 static int dead_code_loop_removed;
76 static int dead_code_loop_executed_once;
77 static int dead_code_statement_removed;
78 static int dead_code_unstructured_if_removed;
79 static int dead_code_unstructured_if_replaced_by_its_effect;
80 static int dead_code_unstructured_if_false_branch_removed;
81 static int dead_code_unstructured_if_true_branch_removed;
82 static void suppress_dead_code_statement(
statement);
87 initialize_dead_code_statistics()
89 dead_code_if_removed = 0;
90 dead_code_if_replaced_by_its_effect = 0;
91 dead_code_if_false_branch_removed = 0;
92 dead_code_if_true_branch_removed = 0;
93 dead_code_loop_removed = 0;
94 dead_code_loop_executed_once = 0;
95 dead_code_statement_removed = 0;
96 dead_code_unstructured_if_removed = 0;
97 dead_code_unstructured_if_replaced_by_its_effect = 0;
98 dead_code_unstructured_if_false_branch_removed = 0;
99 dead_code_unstructured_if_true_branch_removed = 0;
104 display_dead_code_statistics()
107 int elimination_count = dead_code_statement_removed
108 + dead_code_loop_removed
109 + dead_code_loop_executed_once
110 + dead_code_if_removed
111 + dead_code_if_replaced_by_its_effect;
112 elimination_count += dead_code_unstructured_if_removed
113 + dead_code_unstructured_if_replaced_by_its_effect;
115 if (elimination_count > 0)
117 user_log(
"* %d dead code part%s %s been discarded. *\n",
119 elimination_count > 1 ?
"s" :
"",
120 elimination_count > 1 ?
"have" :
"has");
122 user_log(
"Statements removed (directly dead): %d\n",
123 dead_code_statement_removed);
125 user_log(
"Loops: loops removed: %d, loops executed only once: %d\n",
126 dead_code_loop_removed, dead_code_loop_executed_once);
128 user_log(
"Structured tests: \"if\" removed: %d, "
129 "\"if\" replaced by side effects: %d\n"
130 "\t(\"then\" removed: %d, "
131 "\"else\" removed: %d)\n",
132 dead_code_if_removed, dead_code_if_replaced_by_its_effect,
133 dead_code_if_true_branch_removed,
134 dead_code_if_false_branch_removed);
136 user_log(
"Unstructured tests: \"if\" removed: %d, "
137 "\"if\" replaced by side effects: %d\n"
138 "\t(unstructured \"then\" removed: %d, "
139 "unstructured \"else\" removed: %d)\n",
140 dead_code_unstructured_if_removed,
141 dead_code_unstructured_if_replaced_by_its_effect,
142 dead_code_unstructured_if_true_branch_removed,
143 dead_code_unstructured_if_false_branch_removed);
153 static void stdebug(
int dl,
string msg,
statement s)
171 stdebug(9,
"dead_test_filter: then branch", st_true);
172 stdebug(9,
"dead_test_filter: else branch", st_false);
176 transformer pretrue = get_statement_precondition(st_true);
177 transformer prefalse = get_statement_precondition(st_false);
178 fprintf(stderr,
"NN true and false branches");
205 static bool discard_statement_and_save_label_and_comment(
statement s)
273 discard_statement_and_save_label_and_comment(st);
300 bool feasible_p =
true;
387 stdebug(4,
"remove_loop_statement", s);
404 bool m3_negatif =
false, m3_positif =
false;
405 volatile bool retour;
421 pre = get_statement_precondition(s);
441 if (retour)
return true;
447 ps =
sc_dup(precondition_ps);
448 sc_add_ineg(ps, pc3);
459 pips_debug(2,
"loop_increment_value positif = %d, negatif = %d\n",
460 m3_positif, m3_negatif);
582 stdebug(9,
"remove_dead_loop: New value of statement", s);
589 static bool statement_write_effect_p(
statement s)
591 bool write_effect_found =
false;
597 write_effect_found =
true;
602 return write_effect_found;
612 static void remove_if_statement_according_to_write_effects
613 (
statement s,
bool this_test_is_unstructured_p)
617 pips_assert(
"statement is consistent at entry", s);
619 if (statement_write_effect_p(s)) {
631 if (this_test_is_unstructured_p)
632 dead_code_unstructured_if_replaced_by_its_effect++;
634 dead_code_if_replaced_by_its_effect++;
636 pips_assert(
"statement is consistent after partial dead code removeal", s);
643 if (this_test_is_unstructured_p)
644 dead_code_unstructured_if_removed++;
646 dead_code_if_removed++;
649 pips_assert(
"statement is consistent after dead code removal", s);
670 static bool dead_deal_with_test(
statement s,
683 what_is_dead = dead_test_filter(st_true, st_false);
685 switch (what_is_dead) {
691 remove_if_statement_according_to_write_effects(s,
701 suppress_dead_code_statement(st_false);
702 dead_code_if_true_branch_removed++;
710 remove_if_statement_according_to_write_effects(s,
719 suppress_dead_code_statement(st_true);
720 dead_code_if_false_branch_removed++;
728 pips_assert(
"dead_deal_with_test does not understand dead_test_filter()",
749 pips_assert(
"Preconditions are defined for all statements",
814 pips_assert(
"unstructured is consistent at the beginning",
823 pips_debug(3,
"(gen_length(control_successors(c)) = %d)\n",
824 number_of_successors);
827 if (number_of_successors == 0 || number_of_successors == 1) {
831 suppress_dead_code_statement(st);
833 else if (number_of_successors == 2
844 switch (dead_unstructured_test_filter(st)) {
847 pips_assert(
"unstructured is consistent before then is dead",
856 pips_assert(
"unstructured is consistent after then_is_dead",
859 remove_if_statement_according_to_write_effects
862 pips_assert(
"unstructured is consistent after then_is_dead",
865 some_unstructured_ifs_have_been_changed =
true;
866 dead_code_unstructured_if_true_branch_removed++;
868 pips_assert(
"unstructured is consistent after then_is_dead",
874 pips_assert(
"unstructured is consistent before else_is_dead",
883 remove_if_statement_according_to_write_effects
886 some_unstructured_ifs_have_been_changed =
true;
887 dead_code_unstructured_if_false_branch_removed++;
889 pips_assert(
"unstructured is consistent after else_is_dead",
899 if (true_control==false_control)
904 remove_if_statement_according_to_write_effects
907 some_unstructured_ifs_have_been_changed =
true;
908 dead_code_unstructured_if_false_branch_removed++;
920 pips_assert(
"unstructured is consistent after some iterations",
925 pips_assert(
"unstructured is consistent at the end",
929 static bool zero_or_one_iteration_while_loop_p(
statement s,
bool one_p)
934 bool one_iteration_p =
false;
935 bool zero_iteration_p =
false;
992 bool zero_or_one_iteration_p = one_p? one_iteration_p : zero_iteration_p;
993 return zero_or_one_iteration_p;
996 static bool one_iteration_while_loop_p(
statement s)
998 bool one_p = zero_or_one_iteration_while_loop_p(s,
true);
1002 static bool zero_iteration_while_loop_p(
statement s)
1004 bool zero_p = zero_or_one_iteration_while_loop_p(s,
false);
1013 static void simplify_while_loop(
statement s)
1018 bool one_iteration_p = one_iteration_while_loop_p(s);
1019 bool zero_iteration_p = zero_iteration_while_loop_p(s);
1071 else if(zero_iteration_p && !side_effect_p) {
1089 pips_debug(2,
"Begin for statement %td (%td, %td)\n",
1094 stdebug(2,
"dead_statement_rewrite: "
1095 "The current statement st at the beginning",
1115 simplify_while_loop(s);
1123 stdebug(9,
"dead_statement_rewrite: test", s);
1133 stdebug(9,
"dead_statement_rewrite: ", s);
1135 remove_if_statement_according_to_write_effects
1161 pips_debug(2,
"End for statement %td (%td, %td)\n",
1165 stdebug(2,
"dead_statement_rewrite: The current statement st at the end", s);
1170 static bool dead_statement_filter(
statement s)
1183 pips_debug(2,
"Begin for statement %td (%td, %td)\n",
1194 stdebug(9,
"dead_statement_filter: The current statement", s);
1203 pips_debug(2,
"This statement is likely unreachable. Skip...\n");
1219 pips_debug(2,
"Ignored statement %td (%td, %td)\n",
1223 retour = discard_statement_and_save_label_and_comment(s);
1224 dead_code_statement_removed++;
1248 pips_debug(2,
"Dead statement %td (%td, %td)\n",
1252 retour = discard_statement_and_save_label_and_comment(s);
1253 dead_code_statement_removed++;
1260 pips_debug(2,
"Dead sequence statement %td (%td, %td)\n",
1264 retour = discard_statement_and_save_label_and_comment(s);
1265 dead_code_statement_removed++;
1271 if (dead_loop_p(l)) {
1272 pips_debug(2,
"Dead loop %s at statement %td (%td, %td)\n",
1278 retour = remove_dead_loop(s, i, l);
1279 dead_code_loop_removed++;
1282 else if (loop_executed_once_p(s, l)) {
1287 "loop %s at %td (%td, %td) executed once and only once\n",
1293 stdebug(9,
"dead_statement_filter", s);
1296 remove_loop_statement(s, i, l);
1297 dead_code_loop_executed_once++;
1298 stdebug(9,
"dead_statement_filter: out remove_loop_statement", s);
1300 suppress_dead_code_statement(body);
1320 retour = dead_deal_with_test(s, t);
1353 dead_code_statement_removed++;
1360 dead_code_statement_removed++;
1371 pips_assert(
"statement s is consistent before rewrite",
1374 if (retour ==
false) {
1378 dead_statement_rewrite(s);
1381 pips_debug(2,
"End for statement %td (%td, %td): %s going down\n",
1385 retour?
"" :
"not");
1387 pips_assert(
"statement s is consistent at the end",
1395 static void suppress_dead_code_statement(
statement mod_stmt)
1400 dead_statement_filter(mod_stmt);
1406 dead_statement_rewrite(mod_stmt);
1411 static bool remove_useless_label_internal(
statement);
1416 static bool generic_simplify_control(
1417 const string mod_name,
bool use_precondition_p)
1424 " unit ! Abort...");
1443 if (use_precondition_p) {
1455 debug_on(
"SIMPLIFY_CONTROL_DEBUG_LEVEL");
1465 initialize_dead_code_statistics();
1466 some_unstructured_ifs_have_been_changed =
false;
1469 suppress_dead_code_statement(mod_stmt);
1474 display_dead_code_statistics();
1490 if(use_precondition_p) {
1498 if (some_unstructured_ifs_have_been_changed)
1516 return generic_simplify_control(mod_name,
true);
1531 get_statement_precondition = load_identity_precondition;
1532 return generic_simplify_control(mod_name,
false);
1541 "This phase has been renamed, please use 'simplify_control'"
1542 " from now. The old alias 'suppress_dead_code' might be removed soon.\n" );
1546 static bool remove_useless_label_internal(
statement s)
1548 bool changed =
false;
void user_log(const char *format,...)
void free_transformer(transformer p)
bool instruction_consistent_p(instruction p)
bool unstructured_consistent_p(unstructured p)
expression copy_expression(expression p)
EXPRESSION.
bool statement_consistent_p(statement p)
void free_instruction(instruction p)
void free_statement(statement p)
static statement module_statement
transformer transformer_dup(transformer t_in)
transformer package - basic routines
transformer transformer_identity()
Allocate an identity transformer.
callees compute_callees(const statement stat)
Recompute the callees of a module statement.
bool clean_up_sequences_internal(statement s)
An entry point for internal usage, such as from take_out_the_exit_node_if_not_a_continue():
void initialize_clean_up_sequences_statistics(void)
bool clean_up_sequences(statement s)
Recursively clean up the statement sequences by fusing them if possible and by removing useless one.
void display_clean_up_sequences_statistics(void)
struct _newgen_struct_statement_ * statement
entity int_to_entity(_int c)
Pcontrainte contrainte_make(Pvecteur pv)
Pcontrainte contrainte_make(Pvecteur pv): allocation et initialisation d'une contrainte avec un vecte...
Pcontrainte contrainte_free(Pcontrainte c)
Pcontrainte contrainte_free(Pcontrainte c): liberation de l'espace memoire alloue a la contrainte c a...
bool unspaghettify(const string)
Try to simplify the control graph of a module by removing useless CONTINUEs, unreachable code.
list load_proper_rw_effects_list(statement)
void reset_proper_rw_effects(void)
void set_proper_rw_effects(statement_effects)
void set_cumulated_rw_effects(statement_effects)
void store_cumulated_rw_effects_list(statement, list)
list load_cumulated_rw_effects_list(statement)
effects load_cumulated_rw_effects(statement)
void reset_cumulated_rw_effects(void)
bool expression_with_side_effect_p(expression)
#define action_write_p(x)
#define effects_effects(x)
bool compilation_unit_p(const char *module_name)
The names of PIPS entities carry information about their nature.
const char * module_name(const char *s)
Return the module part of an entity name.
bool get_bool_property(const string)
FC 2015-07-20: yuk, moved out to prevent an include cycle dependency include "properties....
#define gen_context_recurse(start, ctxt, domain_number, flt, rwt)
#define gen_recurse(start, domain_number, flt, rwt)
statement instruction_to_statement(instruction)
Build a statement from a give instruction.
void control_map_get_blocs(control c, list *l)
Build recursively the list of all controls reachable from a control of an unstructured.
void reset_current_module_entity(void)
Reset the current module entity.
void reset_current_module_statement(void)
Reset the current module statement.
statement set_current_module_statement(statement)
Set the current module statement.
entity set_current_module_entity(entity)
static.c
entity get_current_module_entity(void)
Get the entity of the current module.
void replace_entity(void *s, entity old, entity new)
per variable version of replace_entities.
bool gen_true2(__attribute__((unused)) gen_chunk *u1, __attribute__((unused)) void *u2)
instruction make_instruction_block(list statements)
Build an instruction block from a list of statements.
instruction make_continue_instruction()
Creates a CONTINUE instruction, that is the FORTRAN nop, the ";" in C or the "pass" in Python for exa...
instruction make_assign_instruction(expression l, expression r)
#define ENDP(l)
Test if a list is empty.
list gen_nreverse(list cp)
reverse a list in place
void gen_remove_once(list *pl, const void *o)
Remove the first occurence of o in list pl:
#define NIL
The empty list (nil in Lisp)
size_t gen_length(const list l)
#define CONS(_t_, _i_, _l_)
List element cell constructor (insert an element at the beginning of a list)
list gen_nconc(list cp1, list cp2)
physically concatenates CP1 and CP2 but do not duplicates the elements
#define CAR(pcons)
Get the value of the first element of a list.
void gen_free_list(list l)
free the spine of the list
#define FOREACH(_fe_CASTER, _fe_item, _fe_list)
Apply/map an instruction block on all the elements of a list.
#define CDR(pcons)
Get the list less its first element.
list gen_full_copy_list(list l)
Copy a list structure with element copy.
string db_get_memory_resource(const char *rname, const char *oname, bool pure)
Return the pointer to the resource, whatever it is.
#define DB_PUT_MEMORY_RESOURCE(res_name, own_name, res_val)
conform to old interface.
list statement_block(statement)
Get the list of block statements of a statement sequence.
bool empty_statement_or_continue_p(statement)
Return true if the statement is an empty instruction block or a continue or a recursive combination o...
bool statement_loop_p(statement)
bool format_statement_p(statement)
Test if a statement is a Fortran FORMAT.
statement make_assign_statement(expression, expression)
void insert_comments_to_statement(statement, const char *)
Insert a comment string (if non empty) at the beginning of the comments of a statement.
bool statement_may_have_control_effects_p(statement)
list statement_to_direct_declarations(statement)
Returns the declarations contained directly in a statement s.
statement make_continue_statement(entity)
bool empty_comments_p(const char *)
void fix_sequence_statement_attributes(statement)
Since blocks are not represented in Fortran, they cannot carry a label.
bool declaration_statement_p(statement)
Had to be optimized according to Beatrice Creusillet.
entity find_final_statement_label(statement)
Find the label associated with the last statement executed within s.
void statement_remove_useless_label(statement, bool *)
remove the label of a statement if the statement is not unstructured.
#define pips_debug
these macros use the GNU extensions that allow variadic macros, including with an empty list.
#define pips_user_warning
#define pips_assert(what, predicate)
common macros, two flavors depending on NDEBUG
#define pips_internal_error
#define STATEMENT_ORDERING_UNDEFINED
mapping.h inclusion
string concatenate(const char *,...)
Return the concatenation of the given strings.
int f(int off1, int off2, int n, float r[n], float a[n], float b[n])
void print_statement(statement)
Print a statement on stderr.
void insure_return_as_last_statement(entity, statement *)
bool module_reorder(statement body)
Reorder a module and recompute order to statement if any.
#define PLUS_OPERATOR_NAME
#define ORDERING_NUMBER(o)
#define ORDERING_STATEMENT(o)
#define NORMALIZE_EXPRESSION(e)
#define statement_block_p(stat)
#define ENTITY_CONDITIONAL_P(e)
#define unstructured_control
After the modification in Newgen: unstructured = entry:control x exit:control we have create a macro ...
#define instruction_block(i)
#define make_statement_list(stats...)
easy list constructor
#define empty_comments
Empty comments (i.e.
#define ENTITY_FALSE_P(e)
#define make_empty_statement
An alias for make_empty_block_statement.
const char * entity_local_name(entity e)
entity_local_name modified so that it does not core when used in vect_fprint, since someone thought t...
bool c_module_p(entity m)
Test if a module "m" is written in C.
entity module_name_to_entity(const char *mn)
This is an alias for local_name_to_top_level_entity.
entity entity_empty_label(void)
bool entity_empty_label_p(entity e)
entity entity_intrinsic(const char *name)
FI: I do not understand this function name (see next one!).
const char * label_local_name(entity e)
END_EOLE.
bool range_count(range r, intptr_t *pcount)
The range count only can be evaluated if the three range expressions are constant and if the incremen...
bool false_expression_p(expression e)
bool expression_integer_constant_p(expression e)
bool expression_call_p(expression e)
int expression_to_int(expression exp)
================================================================
bool true_expression_p(expression e)
expression entity_to_expression(entity e)
if v is a constant, returns a constant call.
expression make_factor_expression(int coeff, entity vari)
Some functions to generate expressions from vectors and constraint systems.
expression MakeBinaryCall(entity f, expression eg, expression ed)
Creates a call expression to a function with 2 arguments.
bool expression_equal_p(expression e1, expression e2)
Syntactic equality e1==e2.
call expression_call(expression e)
bool expression_reference_p(expression e)
Test if an expression is a reference.
reference expression_reference(expression e)
Short cut, meaningful only if expression_reference_p(e) holds.
basic MakeBasic(int)
END_EOLE.
bool entity_scalar_p(entity)
The concrete type of e is a scalar type.
entity make_new_scalar_variable(entity, basic)
statement pop_statement_global_stack(void)
void push_statement_on_statement_global_stack(statement)
void free_statement_global_stack(void)
void make_statement_global_stack(void)
#define transformer_undefined
#define transformer_undefined_p(x)
#define instruction_sequence_p(x)
#define normalized_linear_p(x)
#define instruction_loop_p(x)
#define reference_variable(x)
#define control_predecessors(x)
#define instruction_loop(x)
#define statement_ordering(x)
#define whileloop_evaluation(x)
#define statement_domain
newgen_sizeofexpression_domain_defined
#define CONTROL(x)
CONTROL.
#define range_increment(x)
#define EXPRESSION(x)
EXPRESSION.
#define instruction_undefined
#define statement_label(x)
#define expression_undefined
@ is_instruction_unstructured
@ is_instruction_whileloop
@ is_instruction_expression
@ is_instruction_sequence
#define instruction_tag(x)
#define transformer_relation(x)
#define control_successors(x)
#define instruction_unstructured_p(x)
#define instruction_call_p(x)
#define instruction_expression(x)
#define test_condition(x)
#define instruction_whileloop(x)
#define whileloop_body(x)
#define statement_declarations(x)
#define statement_instruction(x)
#define statement_comments(x)
#define instruction_call(x)
struct _newgen_struct_transformer_ * transformer
#define instruction_test_p(x)
#define call_arguments(x)
#define control_statement(x)
#define instruction_test(x)
#define whileloop_condition(x)
#define evaluation_after_p(x)
#define statement_number(x)
#define normalized_linear(x)
#define predicate_system(x)
#define instruction_unstructured(x)
#define statement_undefined
#define STATEMENT(x)
STATEMENT.
void sc_rm(Psysteme ps)
void sc_rm(Psysteme ps): liberation de l'espace memoire occupe par le systeme de contraintes ps;
Psysteme sc_dup(Psysteme ps)
Psysteme sc_dup(Psysteme ps): should becomes a link.
bool ineq_redund_with_sc_p(Psysteme sc, Pcontrainte ineq)
This function returns true if the inequation ineq is redundant for the system ps and false otherwise.
bool eq_redund_with_sc_p(Psysteme sc, Pcontrainte eq)
bool eq_redund_with_sc_p(sc, eq) Psysteme sc; Pcontrainte eq;
bool sc_rational_feasibility_ofl_ctrl(Psysteme sc, int ofl_ctrl, bool ofl_res)
Pcontrainte eq
element du vecteur colonne du systeme donne par l'analyse
void sc_fprint(FILE *fp, Psysteme ps, get_variable_name_t nom_var)
void sc_fprint(FILE * f, Psysteme ps, char * (*nom_var)()): cette fonction imprime dans le fichier po...
int fprintf()
test sc_min : ce test s'appelle par : programme fichier1.data fichier2.data ...
void vect_chg_sgn(Pvecteur v)
void vect_chg_sgn(Pvecteur v): multiplie v par -1
transformer precondition_add_condition_information(transformer pre, expression c, transformer context, bool veracity)
context might be derivable from pre as transformer_range(pre) but this is sometimes very computationa...
int simplify_boolean_expression_with_precondition(expression e, transformer p)
Simplification of bool expressions with precondition.
transformer condition_to_transformer(expression cond, transformer pre, bool veracity)
To capture side effects and to add C twist for numerical conditions.
void module_to_value_mappings(entity m)
void module_to_value_mappings(entity m): build hash tables between variables and values (old,...
bool statement_weakly_feasible_p(statement)
utils.c
bool statement_strongly_feasible_p(statement)
Return true if statement s is reachable according to its precondition.
transformer load_statement_precondition(statement)
void set_transformer_map(statement_mapping)
transformer load_statement_transformer(statement)
void reset_precondition_map(void)
void set_precondition_map(statement_mapping)
void reset_transformer_map(void)
bool statement_feasible_p(statement)
Return true if statement s is reachable according to its precondition.
le type des coefficients dans les vecteurs: Value est defini dans le package arithmetique
The structure used to build lists in NewGen.
#define TCST
VARIABLE REPRESENTANT LE TERME CONSTANT.
void * Variable
arithmetique is a requirement for vecteur, but I do not want to inforce it in all pips files....
Pvecteur vect_dup(Pvecteur v_in)
Pvecteur vect_dup(Pvecteur v_in): duplication du vecteur v_in; allocation de et copie dans v_out;.
Pvecteur vect_add(Pvecteur v1, Pvecteur v2)
package vecteur - operations binaires
Pvecteur vect_substract(Pvecteur v1, Pvecteur v2)
Pvecteur vect_substract(Pvecteur v1, Pvecteur v2): allocation d'un vecteur v dont la valeur est la di...
void vect_add_elem(Pvecteur *pvect, Variable var, Value val)
void vect_add_elem(Pvecteur * pvect, Variable var, Value val): addition d'un vecteur colineaire au ve...