/* $Id$ 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 . */ #ifdef HAVE_CONFIG_H #include "pips_config.h" #endif /* Ronan Keryell, 1995. */ #ifndef lint char vcid_unspaghettify[] = "%A% ($Date: 2004/01/23 13:55:04 $, ) version $Revision: 14223 $, got on %D%, %T% [%P%].\n Copyright (c) �cole des Mines de Paris Proprietary."; #endif /* lint */ #include #include #include #include "linear.h" #include "genC.h" #include "ri.h" #include "ri-util.h" #include "workspace-util.h" #include "text-util.h" #include "database.h" #include "misc.h" #include "pipsdbm.h" #include "resources.h" #include "properties.h" #include "control.h" /* Avoid infinite restructuring in some cases: */ enum { N_ITER_RESTRUCTURE_FIX_POINT = 10 }; typedef enum { STRUCTURED_NULL_IF = 1901, STRUCTURED_IF_THEN = 1966, STRUCTURED_IF_ELSE = 1997, STRUCTURED_IF_THEN_ELSE = 2000 } structured_test_type; static bool currently_apply_test_restructuring; static bool currently_apply_recursive_decomposition; /* To print some statistics about control graph restructuration: */ static int number_of_restructured_if_then; static int number_of_restructured_if_else; static int number_of_restructured_if_then_else; static int number_of_restructured_null_if; static int number_of_recovered_do_while; static int number_of_recovered_while; static void initialize_unspaghettify_statistics() { number_of_restructured_if_then = 0; number_of_restructured_if_else = 0; number_of_restructured_if_then_else = 0; number_of_restructured_null_if = 0; number_of_recovered_do_while = 0; number_of_recovered_while = 0; } /* Compute the number of all the computations that have been done */ static int total_number_of_restructurations() { return number_of_restructured_if_then + number_of_restructured_if_else + number_of_restructured_if_then_else + number_of_restructured_null_if + number_of_recovered_do_while + number_of_recovered_while; } static void display_unspaghettify_statistics() { if (currently_apply_test_restructuring && get_bool_property("UNSPAGHETTIFY_DISPLAY_STATISTICS")) { int number_of_restructured_tests = number_of_restructured_if_then + number_of_restructured_if_else + number_of_restructured_if_then_else + number_of_restructured_null_if; user_log("Total number of restructurations: %d\n", total_number_of_restructurations()); if (number_of_restructured_tests != 0) { user_log("%d test%s %s been restructured:\n", number_of_restructured_tests, number_of_restructured_tests > 1 ? "s" : "", number_of_restructured_tests > 1 ? "have" : "has"); user_log("\t %d IF/THEN/ELSE, %d IF/THEN, %d IF/ELSE & %d null IF.\n", number_of_restructured_if_then_else, number_of_restructured_if_then, number_of_restructured_if_else, number_of_restructured_null_if); } if ((number_of_recovered_do_while + number_of_recovered_while) != 0) { user_log("%d structured \"do ... while()\" %s been recovered.\n", number_of_recovered_do_while, number_of_recovered_do_while > 1 ? "have" : "has"); user_log("%d structured \"while() ...\" %s been recovered.\n", number_of_recovered_while, number_of_recovered_while > 1 ? "have" : "has"); } } } /* Remove a useless continue in a sequence of control since it is typically the kind of useless things generated by the controlizer... */ static void remove_useless_continue_or_empty_code_in_unstructured(unstructured u) { list blocs = NIL; list remove_continue_list = NIL; /* The entry point of the unstructured: */ control entry_node = unstructured_control(u); /* and its exit point: */ control exit_node = unstructured_exit(u); pips_debug(7, "Dealing with unstructured %p (begin: %p, end: %p)\n", u, entry_node, exit_node); CONTROL_MAP(c, { ifdebug (1) pips_assert("control is consistent", control_consistent_p(c)); /* Do not remove the exit nor the entry node node since it is boring to relink the entry and exit node... That is not important since there is another pass that fuse the sequences. Dead code elimination should remove these structured CONTINUE afterward... */ if (c != exit_node && c != entry_node) if (gen_length(control_successors(c)) == 1) { /* Do not deal with any number of predecessor since we do not want to remove the node 100 in : goto 100 100 goto 200 200 goto 100 There may be also some unreachable continues, that are without predecessors (0)... We want to remove them also. Well with this modification, I am not sure that this procedure is still useful... So only 0 or 1 predecessor: */ if (gen_length(control_predecessors(c)) <= 1) { statement st = control_statement(c); pips_debug(7, "\tNode %p has candidate links\n", c); if (empty_statement_or_continue_without_comment_p(st)) { /* It is some useless code with no comment to spare: put it in the remove list: */ remove_continue_list = CONS(CONTROL, c, remove_continue_list); pips_debug(7, "\tNode %p for statement %s to be removed\n", c, statement_identification(control_statement(c))); } } } }, entry_node, blocs); gen_free_list(blocs); /* Now we have the list of the control node to discard. Do the cleaning: */ MAPL(a_control_list, { control c = CONTROL(CAR(a_control_list)); debug(3, "remove_useless_continue_or_empty_code_in_unstructured", "Remove control %p for statement %s\n", c, statement_identification(control_statement(c))); remove_a_control_from_an_unstructured(c); }, remove_continue_list); gen_free_list(remove_continue_list); } /* The controlizer of PIPS seems to have a bug: it put an empty successor node to the so-called exit node. Correct this fact: */ static void clean_up_exit_node(unstructured u) { control exit_node = unstructured_exit(u); list l = control_successors(exit_node); if (gen_length(l) >= 1) { control c = CONTROL(CAR(l)); pips_assert("clean_up_exit_node", gen_length(control_successors(exit_node)) == 1 && gen_length(control_successors(c)) == 0 && gen_length(control_predecessors(c)) == 1 && empty_statement_or_continue_p(control_statement(c))); /* Remove the useless node: */ CONTROL_(CAR(control_predecessors(c))) = control_undefined; gen_free_list(control_successors(exit_node)); /* Now the exit node has no longer a successor: */ control_successors(exit_node) = NIL; } pips_assert("clean_up_exit_node", gen_length(control_successors(exit_node)) == 0); } /* Try to transform each control sequence in a single statement instead of a list of control nodes: */ void fuse_sequences_in_unstructured(statement s) { list blocs = NIL; list control_nodes_to_fuse = NIL; unstructured u = instruction_unstructured(statement_instruction(s)); list tl = statement_to_implicit_target_labels(s); /* The entry point of the unstructured: */ control entry_node = unstructured_control(u); /* and its exit point: */ control exit_node = unstructured_exit(u); /* To store the list of the controls to fuse we use a mapping since we need to keep track of eventual previous fuse on a control: */ hash_table controls_to_fuse_with_their_successors = hash_table_make(hash_pointer, 0); bool aggressive_restructure_p = get_bool_property("FUSE_CONTROL_NODES_WITH_COMMENTS_OR_LABEL"); ifdebug(4) { pips_debug(4, "Begin with implicit target labels:"); print_arguments(tl); pips_debug(4, "\n"); } ifdebug (1) pips_assert("unstructured is consistent", unstructured_consistent_p(u)); pips_debug(3, "Unstructured %p\n", u); CONTROL_MAP(c, { statement s = control_statement(c); ifdebug (1) pips_assert("control is consistent", control_consistent_p(c)); pips_debug(3, "Looking for control %p...\n", c); /* ifdebug(5) */ /* print_statement(s); */ /* Select a node with only one successor: */ if (gen_length(control_successors(c)) == 1) { control the_successor = CONTROL(CAR(control_successors(c))); size_t number_of_successors_of_the_successor = gen_length(control_successors(the_successor)); size_t number_of_predecessors_of_the_successor = gen_length(control_predecessors(the_successor)); pips_debug(3, "Control %p: (gen_length(control_successors(c)) == 1), number_of_successors_of_the_successor = %zd, number_of_predecessors_of_the_successor = %zd, the successor is the entry node: %d, empty_statement_or_continue_p(control_statement(c)) = %d\n", c, number_of_successors_of_the_successor, number_of_predecessors_of_the_successor, the_successor == entry_node, aggressive_restructure_p ? empty_statement_or_continue_p(s) : empty_statement_or_continue_without_comment_p(s)); /* Since I use an O(n) algorithm instead of an O(n^2) all this condition must be checked again later since these topological and semantical properties may have changed during the fusion phase. I think it is true because the fused graph is included into the former graph but I am too lazy to write a proof... :-( Have a look to Validation/Control/create.f. */ if ((number_of_successors_of_the_successor <= 1 /* ...Accept the exit node */ && the_successor != entry_node && number_of_predecessors_of_the_successor == 1) || (aggressive_restructure_p ? empty_statement_or_continue_p(s) : empty_statement_or_continue_without_comment_p(s))) { /* Ok, we have found a node in a sequence. Note that we cannot fuse with the entry node since it must keep this role... */ /* But if c is empty, we can fuse it with any successor without changing the semantincs, even if the successor is the entry node. Don't do this if there is a comment since it mess up the original source look-alike. */ /* The fact we can have a cycle is considered a page below... */ /* Put the control in the fuse list. Since no fusing occurs yet, the address of a control node is itself: */ hash_put(controls_to_fuse_with_their_successors, (char *) c, (char *) c); /* Use also a real list to remove the non-determinism of a later HASH_MAP. Note that since it follow a depth-first algorithm, the output program is more likely to be similar to the output, especially with cycles in the control graph: */ control_nodes_to_fuse = CONS(CONTROL, c, control_nodes_to_fuse); } } else { pips_debug(3, "(gen_length(control_successors(c)) == %zd)\n", gen_length(control_successors(c))); } }, entry_node, blocs); gen_free_list(blocs); /* Reverse the list to follow the order of appearance : */ control_nodes_to_fuse = gen_nreverse(control_nodes_to_fuse); /* Now, since we have the list of the control nodes to fuse with their successors, do the fusion: */ MAP(CONTROL, the_original_control, { control a_control_to_fuse; control the_successor; char * its_address_now; char * old_address; its_address_now = hash_get(controls_to_fuse_with_their_successors, (char *) the_original_control); /* Find the address of a control node to fuse even if it has already been fused with predecessors through a transitive closure: */ for(old_address = (char *) the_original_control;;) { pips_debug(3, "Control %p (originally %p):\n", its_address_now, the_original_control); if (old_address == its_address_now /* ...The control node has not been moved */ || !hash_defined_p(controls_to_fuse_with_their_successors, (char *) its_address_now) /* ...or it has not been moved because it is not a control node to fuse anyway. */ ) /* Ok, the node has been located: */ break; else { /* Follow a former control movement: */ old_address = its_address_now; its_address_now = hash_get(controls_to_fuse_with_their_successors, (char *) its_address_now); } } a_control_to_fuse = (control) its_address_now; /* ifdebug(5) { */ /* fprintf(stderr,"Statement with label \"%s\" for control a_control_fo_fuse=%p\n", */ /* entity_local_name(statement_label(control_statement(a_control_to_fuse))), */ /* a_control_to_fuse); */ /* print_statement(control_statement(a_control_to_fuse)); */ /* fprintf(stderr,"Let's print the statement a second time to see its label again:\n"); */ /* print_statement(control_statement(a_control_to_fuse)); */ /* } */ /* ifdebug(6) { */ /* pips_debug(5, "All the unstructured %p:\n", u); */ /* print_statement(s); */ /* } */ ifdebug (3) fprintf(stderr, "Want to fuse control %p\n", a_control_to_fuse); ifdebug (1) pips_assert("control a_control_to_fuse is consistent", control_consistent_p(a_control_to_fuse)); the_successor = CONTROL(CAR(control_successors(a_control_to_fuse))); ifdebug (3) fprintf(stderr, " with control %p\n", the_successor); ifdebug (1) pips_assert("control the_successor is consistent", control_consistent_p(the_successor)); if (a_control_to_fuse == the_successor) { pips_debug(3, "\tA loop of control has been found... Do not fuse the control %p\n", a_control_to_fuse); } else { int number_of_successors_of_the_successor = gen_length(control_successors(the_successor)); int number_of_predecessors_of_the_successor = gen_length(control_predecessors(the_successor)); /* Verify that the fusion is still valid: */ if ((number_of_successors_of_the_successor <= 1 /* ...Accept the exit node */ && the_successor != entry_node && number_of_predecessors_of_the_successor == 1) || (empty_statement_or_continue_p(control_statement(a_control_to_fuse)) && (!gen_in_list_p(statement_to_label(control_statement(a_control_to_fuse)), tl) /* ||entity_empty_label_p(statement_to_label(control_statement(the_successor)))*/) /* (entity_empty_label_p(statement_to_label(control_statement(a_control_to_fuse))) || entity_empty_label_p(statement_to_label(control_statement(the_successor)))) */ )) { /* Well, it seems to be a real sequence, at most a loop with 2 control nodes... */ pips_debug(3, "\tOk fuse them.\n"); fuse_2_control_nodes(a_control_to_fuse, the_successor); /* make st with the statements of 2 following nodes: */ if (the_successor == entry_node) /* Update the entry node if we fuse with it: */ entry_node = a_control_to_fuse; if (the_successor == exit_node) exit_node = a_control_to_fuse; /* If the node "the_successor" is in the fuse list, we want to keep track of its new place, that is in fact fused in "a_control_to_fuse", so that an eventual fusion will use "a_control_to_fuse" instead of "the_successor": */ if (hash_defined_p(controls_to_fuse_with_their_successors, (char *) the_successor)) { /* Ok, "the_successor" is a node to fuse or that has been already fused (in this case the following is useless, but anyway...). Thus we keep track of its new location: */ hash_update(controls_to_fuse_with_their_successors, (char *) the_successor, (char *) a_control_to_fuse); } } else pips_debug(3, "\tDo not fuse them because the semantics have changed.\n"); } ifdebug (1) pips_assert("control after fuse is consistent", control_consistent_p(a_control_to_fuse)); }, control_nodes_to_fuse); /* Update the potentially modified entry and exit nodes: */ unstructured_control(u)= entry_node; unstructured_exit(u)= exit_node; gen_free_list(tl); hash_table_free(controls_to_fuse_with_their_successors); } /* Take the entry node out of the unstructured if it is not useful, such as not an IF or a node without predecessor. Return true if there is still an unstructured, false if the unstructured has been replaced by a structured statement. If the first node is taked out, then * new_unstructured_statement returns the new statement that own the unstructured, else s. */ static bool take_out_the_entry_node_of_the_unstructured(statement s, statement * new_unstructured_statement) { instruction i = statement_instruction(s); unstructured u = instruction_unstructured(i); control entry_node = unstructured_control(u); list entry_node_successors = control_successors(entry_node); int entry_node_successors_length = gen_length(entry_node_successors); *new_unstructured_statement = s; if (entry_node_successors_length == 2 || gen_length(control_predecessors(entry_node)) > 0) /* Well, this node is useful here since it is an unstructured IF or there is a GOTO on it. */ return true; if (entry_node_successors_length == 0) { /* In fact the unstructured has only one control node! Transform it in a structured block of statements: */ list l = CONS(STATEMENT, control_statement(entry_node), NIL); /* Since the unstructured may have a comment on it, we cannot put the comment on the statement block but on a CONTINUE: */ if (! statement_with_empty_comment_p(s) || ! unlabelled_statement_p(s)) { statement cs = make_continue_statement(statement_label(s)); statement_label(s) = entity_empty_label(); statement_comments(cs) = statement_comments(s); statement_comments(s) = empty_comments; l = CONS(STATEMENT, cs, l); } statement_instruction(s) = make_instruction_block(l); /* Remove the unstructured: */ control_statement(entry_node) = statement_undefined; free_instruction(i); /* No longer unstructured: */ return false; } else { /* Take out the entry node: */ *new_unstructured_statement = instruction_to_statement(i); statement_instruction(s) = make_instruction_block(CONS(STATEMENT, control_statement(entry_node), CONS(STATEMENT, *new_unstructured_statement, NIL))); /* The entry node is now the second node: */ pips_assert("take_out_the_entry_node_of_the_unstructured", entry_node_successors_length == 1); unstructured_control(u) = CONTROL(CAR(entry_node_successors)); discard_a_control_sequence_without_its_statements(entry_node, entry_node); return true; } } /* If the unstructured begin and/or end with a sequence, move the sequence(s) out of the unstructured and return a new statement with an equivalent but more structured code. It returns true if the unstructured has disappeared and else FALSE. If the unstructured is still here, the statement directly owning it is returned in new_unstructured_statement: */ /* Still buggy. No longer used. */ static bool __attribute__ ((unused)) try_to_structure_the_unstructured(statement s, statement * new_unstructured_statement) { control end_of_first_sequence, c; list the_successors, the_predecessors; list begin_statement_list = NIL; list end_statement_list = NIL; control begin_of_last_sequence = control_undefined /* no gcc warning */; instruction i = statement_instruction(s); unstructured u = instruction_unstructured(i); /* The entry point of the unstructured: */ control entry_node = unstructured_control(u); /* and its exit point: */ control exit_node = unstructured_exit(u); /* Find the biggest sequence from the begin: */ if (entry_node == exit_node) /* Well, we have an unstructured with one control node, it is still a sequence: */ end_of_first_sequence = entry_node; else { end_of_first_sequence = control_undefined; for(c = entry_node; gen_length(the_successors = control_successors(c)) <= 1 && gen_length(control_predecessors(c)) <= 1; c = CONTROL(CAR(the_successors))) { end_of_first_sequence = c; if (the_successors == NIL) /* It is in fact the exit_node: */ break; } } if (end_of_first_sequence != control_undefined) /* OK, there is a sequence at the beginning of the unstructured: */ begin_statement_list = generate_a_statement_list_from_a_control_sequence(entry_node, end_of_first_sequence); /* If there is still something in the sequence: */ if (end_of_first_sequence != exit_node) { /* Find the biggest sequence from the end: */ begin_of_last_sequence = control_undefined; for(c = exit_node; gen_length(the_predecessors = control_predecessors(c)) == 1 && gen_length(control_successors(c)) <= 1; c = CONTROL(CAR(the_predecessors))) begin_of_last_sequence = c; /* In fact, an unstructured IF is noted as a control node with 2 successors, that means that we cannot take the biggest sequence since it may move one successor of such an IF and PIPS would be out. */ if (begin_of_last_sequence != control_undefined && gen_length(control_successors(c)) == 2) { /* OK, it is actually an IF before the end sequence. Try to keep a spare node from the sequence. Since the controllizer seems to put always a continue as an IF successor, it is *seems* sensible. */ the_successors = control_successors(begin_of_last_sequence); if (the_successors != NIL) /* There is one successor, that is the sequence has at least 2 control node. Keep the first node as part as IF unstructured: */ begin_of_last_sequence = CONTROL(CAR(the_successors)); else /* There is only one node in the sequence. It remains in the unstructured: */ begin_of_last_sequence = control_undefined; } if (begin_of_last_sequence != control_undefined) /* Then there is a sequence at the end of the unstructured: */ end_statement_list = generate_a_statement_list_from_a_control_sequence(begin_of_last_sequence, exit_node); } /* Now, restructure all the stuff only if there is something to do: */ if (begin_statement_list != NIL || end_statement_list != NIL) { if (end_of_first_sequence == exit_node) { /* All the unstructured is a sequence, replace it with the equivalent block of statement statement: */ statement_instruction(s) = make_instruction_block(begin_statement_list); /* Discard the unstructured instruction: */ discard_an_unstructured_without_its_statements(u); /* Warn that the unstructured no longer exist: */ *new_unstructured_statement = statement_undefined; return true; } else { /* There is still an unstructured, but with one pre- or post-sequence: */ list list_of_the_new_statements; /* Put the unstructured in the new statement list: */ *new_unstructured_statement = instruction_to_statement(i); list_of_the_new_statements = CONS(STATEMENT, *new_unstructured_statement, NIL); if (begin_statement_list != NIL) { /* There is a pre-sequence before the unstructured: */ /* Put the sequence before the unstructured: */ list_of_the_new_statements = gen_nconc(begin_statement_list, list_of_the_new_statements); /* Update the entry node of the unstructured: */ unstructured_control(u) = CONTROL(CAR(control_successors(end_of_first_sequence))); /* Clean up the equivalent control sequence: */ discard_a_control_sequence_without_its_statements(entry_node, end_of_first_sequence); } if (end_statement_list != NIL) { /* There is a post-sequence after the unstructured: */ list_of_the_new_statements = gen_nconc(list_of_the_new_statements, end_statement_list); /* Update the exit node of the unstructured: */ unstructured_exit(u) = CONTROL(CAR(control_predecessors(begin_of_last_sequence))); /* Clean up the equivalent control sequence: */ discard_a_control_sequence_without_its_statements(begin_of_last_sequence, exit_node); } /* Make the instruction of the old statement with the sequence(s) and the stripped-down unstructured: */ statement_instruction(s) = make_instruction_block(list_of_the_new_statements); return false; } } /* By default the unstructured is not changed, thus return the statement owning it: */ *new_unstructured_statement = s; return false; } /* Extract the statement from an exit node of an unstructured statement if it is a useful statement @param s is the statement that contains an unstructured @return the new restructured statement The exit node is the landing pad of the control graph. But if it is not a continue, that means that its statement is a useful instruction at the end of the unstructured and we can take it out of the unstructured. We just return the statement directly containing the unstructured. Right now, it does not extract a RETURN since as explained in � PIPS: Internal Representation of Fortran and C Code � about RETURN_LABEL_NAME in the Entities section, since a RETURN with a label at the exit of un unstructured is always the representation of a RETURN in Fortran unstructured code... So even for C code, a return stay inside an unstructured. RK does not think it is important anyway... */ statement take_out_the_exit_node_if_not_a_continue(statement s) { instruction i = statement_instruction(s); pips_assert("take_out_the_exit_node_if_not_a_continue :" "The statement must be an unstructured", instruction_unstructured_p(i)); /* To return and keep track of the unstructured: */ statement the_unstructured = s; unstructured u = instruction_unstructured(i); control exit_node = unstructured_exit(u); statement the_exit_statement = control_statement(exit_node); instruction the_exit_instruction; /* ifdebug(5) { */ /* pips_debug(5, */ /* "Statement at entry:\n"); */ /* print_statement(s); */ /* } */ /* First, linearize the exit statement since fuse_sequences_in_unstructured() may have gathered many statements in a messy way: */ clean_up_sequences_internal(the_exit_statement); the_exit_instruction = statement_instruction(the_exit_statement); /* Then normalize to have only one non-sequence statement as the exit node: */ if (instruction_sequence_p(the_exit_instruction) && !nop_statement_p(the_exit_statement)) { list first_statement_list; statement first_statement, last_statements; list the_statements = sequence_statements(instruction_sequence(the_exit_instruction)); pips_assert("the_statements must be a true sequence", gen_length(the_statements) >= 2); /* Well, this should be always true if the sequence survived to clean_up_sequences_rewrite()... */ first_statement_list = the_statements; first_statement = STATEMENT(CAR(first_statement_list)); the_statements = CDR(the_statements); CDR(first_statement_list) = NIL; gen_free_list(first_statement_list); last_statements = the_exit_statement; sequence_statements(instruction_sequence(the_exit_instruction)) = the_statements; control_statement(exit_node) = first_statement; /* Then, append the last statements at the end of the unstructured: */ the_unstructured = instruction_to_statement(i); statement_instruction(s) = make_instruction_block(CONS(STATEMENT, the_unstructured, /* ...followed by the last statements: */ CONS(STATEMENT, last_statements, NIL))); /* Fix the variables for the following pass: */ the_exit_statement = first_statement; the_exit_instruction = statement_instruction(the_exit_statement); } /* Here the_exit_statement is not a sequence. */ if (! empty_statement_or_continue_p(the_exit_statement) && ! return_statement_p(the_exit_statement)) { statement new_statement; statement out_keeping; /* Put an empty exit node and keep the statement for the label: */ statement_instruction(the_exit_statement) = make_continue_instruction(); ifdebug (1) pips_assert("Statement is consistent", statement_consistent_p(the_exit_statement)); /* Replace the unstructured by an unstructured followed by the out-keeped instruction: */ new_statement = instruction_to_statement(i); out_keeping = instruction_to_statement(the_exit_instruction); /* Keep track of the statement number: */ statement_number(out_keeping) = statement_number(the_exit_statement); statement_instruction(the_unstructured) = make_instruction_block(CONS(STATEMENT, new_statement, CONS(STATEMENT, out_keeping, NIL))); the_unstructured = new_statement; } /* Heavily rely on a later clean_up_sequences to normalize the above... */ ifdebug (1) pips_assert("Statement is consistent", statement_consistent_p(s)); return the_unstructured; } static void restructure_this_test(control c, structured_test_type t) { statement the_test_statement = control_statement(c); test the_test = instruction_test(statement_instruction(the_test_statement)); control then_node = CONTROL(CAR(control_successors(c))); control else_node = CONTROL(CAR(CDR(control_successors(c)))); statement then_statement = control_statement(then_node); statement else_statement = control_statement(else_node); control test_exit; ifdebug(9) { pips_debug(9, "the test statement:\n"); /* print_statement(the_test_statement); */ pips_assert("Statement is consistent", statement_consistent_p(the_test_statement)); } /* Find the exit node of the test: */ if (t == STRUCTURED_NULL_IF) test_exit = then_node; else if (t == STRUCTURED_IF_THEN || t == STRUCTURED_IF_THEN_ELSE) test_exit = CONTROL(CAR(control_successors(then_node))); else test_exit = CONTROL(CAR(control_successors(else_node))); pips_debug(9, "exit node=%p\n", test_exit); /* Discard and unlink the then_node and else_node if any: */ if (t == STRUCTURED_IF_THEN || t == STRUCTURED_IF_THEN_ELSE) discard_a_control_sequence_without_its_statements(then_node, then_node); if (t == STRUCTURED_IF_ELSE || t == STRUCTURED_IF_THEN_ELSE) discard_a_control_sequence_without_its_statements(else_node, else_node); /* Now rebuild a structured test in the node c from the previous test branch contents: */ if (t == STRUCTURED_IF_THEN || t == STRUCTURED_IF_THEN_ELSE) { free_statement(test_true(the_test)); test_true(the_test) = then_statement; ifdebug(9) { pips_debug(9, "then statement:\n"); /* print_statement(then_statement); */ pips_assert("Statement is consistent", statement_consistent_p(then_statement)); } } if (t == STRUCTURED_IF_ELSE || t == STRUCTURED_IF_THEN_ELSE) { free_statement(test_false(the_test)); test_false(the_test) = else_statement; ifdebug(9) { pips_debug(9, "else statement:\n"); /* print_statement(else_statement); */ pips_assert("Statement is consistent", statement_consistent_p(else_statement)); } } /* Replace the useless CONTINUE by a NOP to improve the prettyprinted code: */ if (t == STRUCTURED_IF_THEN || t == STRUCTURED_NULL_IF) { free_statement(test_false(the_test)); test_false(the_test) = make_empty_statement(); } if (t == STRUCTURED_IF_ELSE || t == STRUCTURED_NULL_IF) { free_statement(test_true(the_test)); test_true(the_test) = make_empty_statement(); } if (t == STRUCTURED_NULL_IF) /* Remove one of the 2 branches, since it is symetrical. In fact, since unlink_2_control_nodes() removes all the redundant branches, need to relink later: */ unlink_2_control_nodes(c, test_exit); if (t == STRUCTURED_IF_THEN_ELSE || t == STRUCTURED_NULL_IF) { /* Relink the structured test node to the successor since both pathes have been removed: */ link_2_control_nodes(c, test_exit); } /* In the other case, the remaining link is just what needed. */ ifdebug(9) { pips_debug(9, "the test statement:\n"); /* print_statement(the_test_statement); */ pips_assert("Statement is consistent", statement_consistent_p(the_test_statement)); } } /* Try to restructure the unstructured IF/THEN/ELSE. Assume that all the sequences has been previously fused. */ static bool restructure_if_then_else(statement s) { list blocs = NIL; bool code_modified_p = false; unstructured u = instruction_unstructured(statement_instruction(s)); /* The entry point of the unstructured: */ control entry_node = unstructured_control(u); /* To store the tests that can be restructured with their test types: */ hash_table structured_tests = hash_table_make(hash_int, 0); pips_assert("Control is consistent", control_consistent_p(entry_node)); /* First mark the IF that can be restructured: */ CONTROL_MAP(c, { /* Only look at test nodes: */ if (gen_length(control_successors(c)) == 2) { control then_node = CONTROL(CAR(control_successors(c))); control else_node = CONTROL(CAR(CDR(control_successors(c)))); int then_node_fan_out = gen_length(control_successors(then_node)); /* Note that if a node is the entry node, its fan in is once more! Nasty bug... */ int then_node_fan_in = gen_length(control_predecessors(then_node)) + (then_node == entry_node); int else_node_fan_out = gen_length(control_successors(else_node)); int else_node_fan_in = gen_length(control_predecessors(else_node)) + (else_node == entry_node); if (then_node == else_node) { /* We've found a structured null if, that is with the then and else branches pointing to the same target: */ hash_put(structured_tests, (char *) c, (char *) STRUCTURED_NULL_IF); number_of_restructured_null_if++; } else if (then_node_fan_out == 1 && else_node_fan_out == 1 && then_node_fan_in == 1 && else_node_fan_in == 1 && CONTROL(CAR(control_successors(then_node))) == CONTROL(CAR(control_successors(else_node)))) { /* We've found a structured if/then/else: */ hash_put(structured_tests, (char *) c, (char *) STRUCTURED_IF_THEN_ELSE); number_of_restructured_if_then_else++; } else if (then_node_fan_out == 1 && then_node_fan_in == 1 && CONTROL(CAR(control_successors(then_node))) == else_node) { /* We've found a structured if/then without else: */ hash_put(structured_tests, (char *) c, (char *) STRUCTURED_IF_THEN); number_of_restructured_if_then++; } else if (else_node_fan_out == 1 && else_node_fan_in == 1 && CONTROL(CAR(control_successors(else_node))) == then_node) { /* We've found a structured if/else without then: */ hash_put(structured_tests, (char *) c, (char *) STRUCTURED_IF_ELSE); number_of_restructured_if_else++; } } }, entry_node, blocs); gen_free_list(blocs); debug(5, "restructure_if_then_else", "%d if/then, %d if/else, %d if/then/else, %d null if\n", number_of_restructured_if_then, number_of_restructured_if_else, number_of_restructured_if_then_else, number_of_restructured_null_if); /* Then restructure if needed: */ HASH_MAP(key, value, { control c = (control) key; structured_test_type t = (structured_test_type) value; /* Hidden in a function to ease debugging... */ restructure_this_test(c, t); /* The code has been modified: */ code_modified_p = true; }, structured_tests); /* Return the number of tests that has been restructured: */ return code_modified_p; } /* Try to recursively restructure the unstructured: */ static void recursively_restructure_an_unstructured(statement s) { /* Used to keep track of the statement that contains directly the unstructured: */ statement new_unstructured_statement; instruction i = statement_instruction(s); if (!instruction_unstructured_p(i)) /* Just stop, it is not or no longer an unstructured. */ return; /* Replace control sequences by simple nodes: */ fuse_sequences_in_unstructured(s); ifdebug(5) { pips_debug(5, "after fuse_sequences_in_unstructured\n"); /* print_statement(s); */ pips_assert("Statement is consistent", statement_consistent_p(s)); } if (take_out_the_entry_node_of_the_unstructured(s, &new_unstructured_statement)) { /* If take_out_the_entry_node_of_the_unstructured() has not been able to discard the unstructured, go on with some other optimizations: */ /* ifdebug(5) { */ /* pips_debug(5, */ /* "after take_out_the_entry_node_of_the_unstructured\n"); */ /* print_statement(s); */ /* } */ new_unstructured_statement = take_out_the_exit_node_if_not_a_continue(new_unstructured_statement); ifdebug(5) { pips_debug(5, "after take_out_the_exit_node_if_not_a_continue\n"); /* print_statement(s); */ pips_assert("Statement is consistent", statement_consistent_p(s)); } /* If we ask for, try to restructure the tests: */ if (currently_apply_test_restructuring && restructure_if_then_else(new_unstructured_statement)) { ifdebug(5) { pips_debug(5, "after restructure_if_then_else\n"); /* print_statement(s); */ pips_assert("Statement is consistent", statement_consistent_p(s)); } /* Well, some tests has been restructured, recurse: */ recursively_restructure_an_unstructured(new_unstructured_statement); } } } /* This is the function that is applied on each statement of the code in a bottom-up way to clean up easy things after the controlizer. Even if we deal with the control graph, that is the "unstructured" instruction, we need to deal with the statement over the unstructured since the restructuration can move some code outside of the unstructured in the statement. */ static void clean_up_control(statement s) { instruction i = statement_instruction(s); if (instruction_unstructured_p(i)) { unstructured u = instruction_unstructured(i); pips_debug(2, "enter\n"); ifdebug (3) { display_linked_control_nodes(unstructured_control(u)); /* fprintf(stderr, "[ The current statement : ]\n"); */ /* print_statement(s); */ } clean_up_exit_node(u); remove_all_unreachable_controls_of_an_unstructured(u); ifdebug(5) { pips_assert("Consistent unstructured", unstructured_consistent_p(u)); pips_debug(5, "after remove_the_unreachable_controls_of_an_unstructured\n"); pips_debug(5, "Accessible nodes from entry:\n"); display_linked_control_nodes(unstructured_control(u)); pips_debug(5, "Accessible nodes from exit:\n"); display_linked_control_nodes(unstructured_exit(u)); /* print_statement(s); */ } remove_useless_continue_or_empty_code_in_unstructured(u); ifdebug(5) { pips_assert("Consistent unstructured", unstructured_consistent_p(u)); pips_debug(5, "after remove_useless_continue_or_empty_code_in_unstructured\n"); /* print_statement(s); */ } pips_debug(2, "exit\n"); } } /* Try to recover structured while loops in an already recursively restructured control graph */ static void recover_structured_while(unstructured u) { control entry_node = unstructured_control(u); control next = CONTROL(CAR(control_successors(entry_node))); size_t arity = gen_length(control_successors(entry_node)); control exit_node = unstructured_exit(u); int line_number; ifdebug (3) { pips_debug(2, "At entry, from the entry node:\n"); display_linked_control_nodes(entry_node); } switch(arity) { case 0: /* It looks like a single node unstructured. Nothing to look at, here. Anyway, it should not exist if the restructured was launched on the graph before... */ return; case 1: /* There is one simple node at unstructured entry: try to detect a "do ... while();" */ if (gen_length(control_successors(next)) != 2) // next is not a test, so no while to be expected here... return; line_number = statement_number(control_statement(next)); test t = instruction_test(statement_instruction(control_statement(next))); expression cond = test_condition(t); control then_c = CONTROL(CAR(control_successors(next))); control else_c = CONTROL(CAR(CDR(control_successors(next)))); if (then_c == entry_node && else_c == exit_node) { /* We have entry: ... if (cond) goto entry; exit: */ // See afterwards to generate the "do ... while(cond)" } else if (then_c == exit_node && else_c == entry_node) { /* We have entry: ... if (cond) goto exit; else goto entry; */ // We need to negate the condition to generate a "do ... while(!cond)" cond = MakeUnaryCall(CreateIntrinsic(C_NOT_OPERATOR_NAME), cond); } else // No "while" detected here: return; /* Build the equivalent " do body; while(cond)". Do not save any label yet, but use the same line number as the "if" one: */ statement body = control_statement(entry_node); statement w = make_whileloop_statement(cond, body, line_number, false); control_statement(entry_node) = w; /* Remove the test control node after having protected recycled old stuff from being discarded: */ test_condition(t) = expression_undefined; remove_a_control_from_an_unstructured_without_relinking(next); /* Relink the remaining nodes in sequence, to be fused later somewhere else: */ link_2_control_nodes(entry_node, exit_node); number_of_recovered_do_while++; break; case 2: { // The entry node is a test. Try to detect a "while() ...;" line_number = statement_number(control_statement(next)); test t = instruction_test(statement_instruction(control_statement(entry_node))); expression cond = test_condition(t); control then_c = CONTROL(CAR(control_successors(entry_node))); control else_c = CONTROL(CAR(CDR(control_successors(entry_node)))); control body_control = control_undefined; statement body = statement_undefined; if (else_c == exit_node) { if (then_c == entry_node) { /* we have: entry: if (cond) goto entry; exit: so we can generate a while(cond); */ } else if (gen_length(control_successors(then_c)) == 1 && CONTROL(CAR(control_successors(then_c))) == entry_node) { /* we have: entry: if (cond) { body goto entry; } exit: so we can generate a while(cond) body; */ body_control = then_c; } else // No while() recognized here... return; } else if (then_c == exit_node) { if (else_c == entry_node) { /* we have: entry: if (cond) goto exit; else goto entry; exit: so we can generate a while(!cond); */ cond = MakeUnaryCall(CreateIntrinsic(C_NOT_OPERATOR_NAME), cond); } else if (gen_length(control_successors(else_c)) == 1 && CONTROL(CAR(control_successors(else_c))) == entry_node) { /* we have: entry: if (cond) goto exit; else { body goto entry; } exit: so we can generate a while(!cond) body; */ body_control = else_c; cond = MakeUnaryCall(CreateIntrinsic(C_NOT_OPERATOR_NAME), cond); } else // No while() recognized here... return; } else // No while() recognized here... return; if (body_control != control_undefined) { // Keep the body to put it in the while later: body = control_statement(body_control); // Remove the control node of the body: control_statement(body_control) = statement_undefined; remove_a_control_from_an_unstructured_without_relinking(body_control); } else { // Make an empty body for the loop: body = make_continue_statement(entity_empty_label()); // Remove the arc from the "if" to itself: unlink_2_control_nodes(entry_node, entry_node); } /* Build the equivalent "while(cond) body;". Do not save any label yet, but use the same line number as the "if" one: */ statement w = make_whileloop_statement(cond, body, line_number, true); // Remove the test node and replace it by the "while": test_condition(t) = expression_undefined; free_statement(control_statement(entry_node)); control_statement(entry_node) = w; /* Other restructuring is applied afterwards to replace the unstructured by a simple statement, the entry and the exit are still linked into a lazy sequence. */ number_of_recovered_while++; break; } default: // This case is not expected in the RI! pips_internal_error("A node cannot have %zd successors!", arity); } // If we land here, the restructuring has taken place above... /* Increase the statistics. Used to rerun a restrustructuring shot after a modification too: */ ifdebug (3) { pips_debug(2, "After while recovering, from the entry node:\n"); display_linked_control_nodes(unstructured_control(u)); } } /* The entry point common to unspaghettify or restructure a module: */ void unspaghettify_or_restructure_statement(statement mod_stmt) { /* Track the number of restructurations done for a fix point: */ int nr = 0; int old_nr; /* To track the number of restructuring iterations: */ int iter = 0; // Note that this debug is not controlled by "UNSPAGHETTIFY_DEBUG_LEVEL": /* ifdebug(5) { */ /* pips_debug(5, "Statement before unspaghettify_or_restructure_statement:\n"); */ /* print_statement(mod_stmt); */ /* } */ debug_on("UNSPAGHETTIFY_DEBUG_LEVEL"); ifdebug (1) pips_assert("Statement is consistent", statement_consistent_p(mod_stmt)); if (get_bool_property("GATHER_FORMATS_AT_BEGINNING")) put_formats_at_module_beginning(mod_stmt); else if (get_bool_property("GATHER_FORMATS_AT_END")) put_formats_at_module_end(mod_stmt); ifdebug (1) pips_assert("Statement is consistent", statement_consistent_p(mod_stmt)); initialize_unspaghettify_statistics(); do { old_nr = nr; /* Split the recursion in three parts to fit in my brain: */ /* First, clean up easy things done by the controlizer: */ gen_recurse(mod_stmt, statement_domain, gen_true, clean_up_control); ifdebug (1) pips_assert("Statement is consistent", statement_consistent_p(mod_stmt)); if (currently_apply_recursive_decomposition) { /* Then try to hierarchize the control flow: */ gen_recurse(mod_stmt, unstructured_domain, gen_true, control_graph_recursive_decomposition); ifdebug (1) pips_assert("Statement is consistent", statement_consistent_p(mod_stmt)); } /* Now apply some local rule, such as if/then/else restructuring and so on: */ gen_recurse(mod_stmt, statement_domain, gen_true, recursively_restructure_an_unstructured); ifdebug (1) pips_assert("Statement is consistent", statement_consistent_p(mod_stmt)); if (get_bool_property("UNSPAGHETTIFY_WHILE_RECOVER")) gen_recurse(mod_stmt, unstructured_domain, gen_true, recover_structured_while); /* End by removing parasitic sequences: */ clean_up_sequences(mod_stmt); ifdebug (1) pips_assert("Statement is consistent", statement_consistent_p(mod_stmt)); /* If something changed, retry further restructuring: */ nr = total_number_of_restructurations(); ifdebug(2) display_unspaghettify_statistics(); } while (nr != old_nr && ++iter < N_ITER_RESTRUCTURE_FIX_POINT); if (nr != old_nr) pips_user_warning("Possible infinite loop restructuring found.\n"); pips_debug(2, "done\n"); display_unspaghettify_statistics(); debug_off(); // Note that this debug is not controlled by "UNSPAGHETTIFY_DEBUG_LEVEL": /* ifdebug(5) { */ /* pips_debug(5, "Statement after unspaghettify_or_restructure_statement:\n"); */ /* print_statement(mod_stmt); */ /* } */ } /* The real entry point of unspaghettify: */ void unspaghettify_statement(statement mod_stmt) { currently_apply_test_restructuring = get_bool_property("UNSPAGHETTIFY_TEST_RESTRUCTURING"); currently_apply_recursive_decomposition = get_bool_property("UNSPAGHETTIFY_RECURSIVE_DECOMPOSITION"); unspaghettify_or_restructure_statement(mod_stmt); } /* A simple cleaning of the control graph without major topological restructuring. Used by example by PHRASE. */ void simple_restructure_statement(statement mod_stmt) { currently_apply_test_restructuring = false; currently_apply_recursive_decomposition = false; unspaghettify_or_restructure_statement(mod_stmt); } /* Try to simplify the control graph of a module by removing useless CONTINUEs, unreachable code. Try to structure a little bit more and so on according to some properties. Unspaguettify is now targetted to be included in the controlizer. */ bool unspaghettify(const string mod_name) { statement mod_stmt; /* Get the true resource, not a copy. */ mod_stmt = (statement) db_get_memory_resource(DBR_CODE, mod_name, true); set_current_module_statement(mod_stmt); set_current_module_entity(local_name_to_top_level_entity(mod_name)); unspaghettify_statement(mod_stmt); /* Reorder the module, because new statements may have been changed. */ module_reorder(mod_stmt); DB_PUT_MEMORY_RESOURCE(DBR_CODE, strdup(mod_name), mod_stmt); reset_current_module_statement(); reset_current_module_entity(); return true; } /* The real entry point of control graph restructuring: */ void restructure_statement(statement mod_stmt) { currently_apply_test_restructuring = true; currently_apply_recursive_decomposition = true; unspaghettify_or_restructure_statement(mod_stmt); } /* Try to simplify the control graph of a module by removing useless CONTINUEs, unreachable code, etc. as in unspaghettify. Do also test restructuring and control graph recursive graph decomposition. */ bool restructure_control(const string mod_name) { statement mod_stmt; /* Get the true resource, not a copy. */ mod_stmt = (statement) db_get_memory_resource(DBR_CODE, mod_name, true); set_current_module_statement(mod_stmt); set_current_module_entity(local_name_to_top_level_entity(mod_name)); restructure_statement(mod_stmt); /* Reorder the module, because new statements may have been changed. */ module_reorder(mod_stmt); DB_PUT_MEMORY_RESOURCE(DBR_CODE, strdup(mod_name), mod_stmt); reset_current_module_statement(); reset_current_module_entity(); return true; }