cfg.c

Go to the documentation of this file.

/*
 
  $Id: cfg.c 23065 2016-03-02 09:05:50Z coelho $
 
  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 <http://www.gnu.org/licenses/>.
 
*/
#ifdef HAVE_CONFIG_H
    #include "pips_config.h"
#endif
/* Basic functions about control flow graphs (CFG), aka unstructured data structure
 *
 * Francois Irigoin, 1997.
 */
 
#include <stdlib.h>
#include <stdio.h>
 
#include "linear.h"
 
#include "genC.h"
#include "misc.h"
#include "ri.h"
#include "ri-util.h"
#include "control.h"
 
/* Check some nice properties expected to be true after a powerful
 * enough controlizer phase.
 *
 * The calls to pips_assert could be replaced by calls to user_warning,
 * the control graph could be printed out before core dumping,...
 *
 * See also check_control_coherency().
 */
bool
unstructured_consistency_p(unstructured u, bool assert_p)
{
    control entry_node = unstructured_control(u);
    control exit_node = unstructured_exit(u);
    bool consistency_p = true;
    list nodes = NIL;
 
    forward_control_map_get_blocs(entry_node, &nodes);
 
    /* the exit and entry nodes must be different or the
     * unstructured would have been reduced to one structured statement
     */
    if(exit_node==entry_node) {
        consistency_p = false;
        if(assert_p) pips_assert("Entry and exit nodes are different", false);
    }
 
    /* The entry node must have at least one predecessor:
     * else it should have been moved out of the unstructured.
     * Note that it has in fact TWO predecessors since it is the
     * unstructured entry point.
     */
    if(consistency_p && ENDP(control_predecessors(entry_node))) {
        consistency_p = false;
        if(assert_p) pips_assert("Entry node has at least one predecessor", false);
    }
 
    /* The exit node should have no successors: its real successor
     * is the statement following the unstructured
     */
    if(consistency_p && !ENDP(control_successors(exit_node))) {
        consistency_p = false;
        if(assert_p) pips_assert("Exit node has no successor", false);
    }
 
    /* The exit node should not be a test:
     * else one of its successors should be control_undefined
     * since it would be outside of the unstructured, or the
     * exit condition would be unknown.
     */
    if(consistency_p) {
        statement exit_s = control_statement(exit_node);
        if(statement_test_p(exit_s)) {
            consistency_p = false;
            if(assert_p) pips_assert("Exit node is not a test", false);
        }
    }
 
    /* The exit node may have no predecessor because an infinite loop
     * appears in the code. Or it is a successor of the entry node.
     */
    if(consistency_p && !ENDP(control_predecessors(exit_node))) {
        if(gen_find_eq(exit_node, nodes)!=exit_node) {
            consistency_p = false;
            if(assert_p) pips_assert("Exit node has predecessors but is unreachable", false);
        }
    }
 
    /* RK: ??? If the exit node is unreachable, it should be a CONTINUE
     * Since a CONTINUE has no effects, it does not perturb analyses even
     * if they do not check reachability.
     * RK: The NOP might be the empty sequence instead of a CONTINUE?
     */
    if(consistency_p && ENDP(control_predecessors(exit_node))) {
        statement exit_s = control_statement(exit_node);
 
        if(!continue_statement_p(exit_s)) {
            consistency_p = false;
            if(assert_p) pips_assert("Unreachable exit node is a CONTINUE statement", false);
        }
    }
 
    /* If the exit node has only one predecessor, it should
     * be a test or the exit node would have been moved outside of
     * the unstructured.
     */
    if(consistency_p && gen_length(control_predecessors(exit_node))==1) {
        control c = CONTROL(CAR(control_predecessors(exit_node)));
        statement s = control_statement(c);
 
        if(!statement_test_p(s)) {
            consistency_p = false;
            if(assert_p) pips_assert("Unique predecessor of exit node is a test", false);
        }
    }
 
    /* Since sequences are merged into a unique node, if a node c1 has only one
     * successor c2, and if c2 has only one predecessor c3, c3 must be c1
     * and either c1 is the exit node which is impossible because there
     * would be no exit condition and the exit node would have a
     * successor, c2, or c2 is the entry node. So c2 must be the entry node.
     *
     * Well, this is not true because only tests can have two successors.
     * hence, a test node cannot be merged.
     */
    MAP(CONTROL, c1, {
        if(gen_length(control_successors(c1))==1) {
            control c2 = CONTROL(CAR(control_successors(c1)));
            statement s2 = control_statement(c2);
 
            if(gen_length(control_predecessors(c2))==1) {
                control c3 = CONTROL(CAR(control_predecessors(c2)));
                if(c1!=c3) {
                    consistency_p = false;
                    if(assert_p) {
                        (void) fprintf(stderr,
                                       "\nEntry node: %p\nExit node: %p\n"
                                       "c1 node: %p\nc2 node: %p\nc3 node: %p\n",
                                       entry_node, exit_node, c1, c2, c3);
                        display_linked_control_nodes(entry_node);
                        pips_assert("c3, the unique predecessor of the unique successor of c1, is c1",
                                    false);
                    }
                }
                else if(c2!=entry_node && !statement_test_p(s2)) {
                    consistency_p = false;
                    if(assert_p) {
                        (void) fprintf(stderr,
                                       "\nEntry node: %p\nExit node: %p\nc1 node: %p\nc2 node: %p\n\n",
                                       entry_node, exit_node, c1, c2);
                        display_linked_control_nodes(entry_node);
                        pips_assert("c2 is the unique successor of c1. "
                                    "c2 has c1 as unique predecessor. c2 must be the entry node",
                                    false);
                    }
                }
            }
 
        }
        }, nodes)
 
    gen_free_list(nodes);
 
    return consistency_p;
}
 
 
/* Test if an unstructured is found to be like a structured while-loop */
bool
unstructured_while_p(unstructured u)
{
    control entry_node = unstructured_control(u);
    control exit_node = unstructured_exit(u);
    bool while_p = false;
 
    ifdebug(5) {
        debug(5, "unstructured_while_p", "Begin with graph\n");
        (void) fprintf(stderr,
                       "\nEntry node: %p\nExit node: %p\n\n",
                       entry_node, exit_node);
        display_linked_control_nodes(entry_node);
    }
 
    /* Make sure that the unstructured has been "normalized" */
    /* while_p = unstructured_consistency_p(u, true); */
    while_p = unstructured_consistency_p(u, false);
 
    /* An unstructured is a while loop if and only if the exit node
     * has only one predecessor and if the entry node is a successor
     * of the predecessor of the exit node.
     *
     * A loop with two exit conditions is not recognized as a while loop.
     *
     * A loop with an exit test on entry, a final exit test (do...while) or
     * an exit test anywhere is recognized as a while loop.
     */
 
    if(while_p && gen_length(control_predecessors(exit_node))==1) {
        control pred = CONTROL(CAR(control_predecessors(exit_node)));
        list succs = NIL;
 
        forward_control_map_get_blocs(pred, &succs);
 
        if(gen_find_eq(entry_node, succs)==entry_node) {
            while_p = true;
        }
        gen_free_list(succs);
    }
    else {
        while_p = false;
    }
 
    debug(5, "unstructured_while_p", "End with while_p=%s\n", bool_to_string(while_p));
 
    return while_p;
}