unreachable.c File Reference

#include <stdio.h>
#include <string.h>
#include "linear.h"
#include "genC.h"
#include "misc.h"
#include "ri.h"
#include "ri-util.h"

Include dependency graph for unreachable.c:

Go to the source code of this file.

Macros
#define	reached_p(s)   (bound_reached_p(s))
	A mapping to store if a given statement is reachable from the control flow point of view: More...
#define	continued_p(s)   (load_continued(s))
#define	check_recursion(s)

Functions
static bool	propagate (statement s)
	returns whether propagation is continued after s. More...
static bool	control_propagate (control c)
void	init_reachable (statement start)
	Compute reachable infomation from the. More...
bool	statement_reachable_p (statement s)
	Test if the given statement is reachable from some statements given at init_reachable(start) More...
bool	statement_continued_p (statement s)
	Test if the execution goes on after the given statement. More...
void	close_reachable (void)
	Remove reachability information about previously checked statements. More...

Macro Definition Documentation

check_recursion

#define check_recursion

(

s

)

Value:

  do {                                                                  \
    if (reached_p(s)) {                                                 \
      if (bound_continued_p(s)) {                                       \
         pips_debug(5, "Statement %p already seen, thus stop recursion.\n", s); \
         return continued_p(s); /**already computed */                  \
      }                                                                 \
      else {                                                            \
        pips_debug(5, "Statement %p marked as reached but the execution does not continue on afterwards.\n\tSo return FALSE.\n", s); \
        return false; /**avoids an infinite recursion... */             \
      }                                                                 \
    }                                                                   \
    else {                                                              \
      pips_debug(5, "New statement %p marked as reached.\n", s);        \
      store_reached(s, true);                                           \
    }                                                                   \
  } while (false) /**Pattern to be able to use this macro like an instruction. */

Definition at line 55 of file unreachable.c.

continued_p

#define continued_p

(

s

)

(load_continued(s))

Definition at line 51 of file unreachable.c.

reached_p

#define reached_p

(

s

)

(bound_reached_p(s))

A mapping to store if a given statement is reachable from the control flow point of view:

Definition at line 50 of file unreachable.c.

Function Documentation

close_reachable()

void close_reachable

(

void

)

Remove reachability information about previously checked statements.

Definition at line 252 of file unreachable.c.

{
    close_reached();
    close_continued();
}

Referenced by module_name_to_preconditions(), and module_name_to_total_preconditions().

Here is the caller graph for this function:

control_propagate()

static bool control_propagate ( control  c )

static

If we already have dealt with the current control node, stop the recursion:

already computed

Investigate about the continuation status of the statement:

Investigate the control successors only if the current one continues afterwards

It seems like a fallacy here. It is not semantically different if we have a cycle with more than 1 goto... It does not work for irreductible graphs either but it is detected anyway now in proagate(). RK

1 GO TO 1

Definition at line 74 of file unreachable.c.

{
  list lc = control_successors(c);
  int len = gen_length(lc);
  statement s = control_statement(c);
  pips_assert("max 2 successors", len<=2);
  pips_debug(1, "Entering control_propagate for control %p\n", c);
 
  /* If we already have dealt with the current control node, stop the
     recursion: */
  if (reached_p(s) && bound_continued_p(s)) {
    /* already computed */
    pips_debug(5, "Statement %p already seen, thus stop recursion.\n", s);
    return continued_p(s);
  }                                                                     \
  /* Investigate about the continuation status of the statement: */
  bool continued = propagate(s);
 
  if (continued) {
    /* Investigate the control successors only if the current one
       continues afterwards */
    if (len==2) {
      bool ctrue, cfalse;
      ctrue = control_propagate(CONTROL(CAR(lc)));
      cfalse = control_propagate(CONTROL(CAR(CDR(lc))));
      // Continue after the test only if at leat one branch goes on:
      continued = ctrue || cfalse;
    }
    else if (len==1) {
      control cn = CONTROL(CAR(lc));
      if (cn!=c) continued = control_propagate(cn);
      /* It seems like a fallacy here. It is not semantically different if
         we have a cycle with more than 1 goto... It does not work for
         irreductible graphs either but it is detected anyway now in
         proagate(). RK */
      else continued = false; /* 1 GO TO 1 */
    }
  }
  pips_debug(1, "Ending control_propagate for control %p and statement %p returning continued %d\n",
             c, s, continued);
  //  store_continued(control_statement(c), continued);
  return continued;
}

References CAR, CDR, continued_p, CONTROL, control_statement, control_successors, gen_length(), pips_assert, pips_debug, propagate(), and reached_p.

Referenced by propagate().

Here is the call graph for this function:

Here is the caller graph for this function:

init_reachable()

void init_reachable

(

statement

start

)

Compute reachable infomation from the.

unreachable.c

Parameters

start

statement.

Parameters

start

tart

Definition at line 223 of file unreachable.c.

                                     {
  debug_on("REACHABLE_DEBUG_LEVEL");
  init_reached();
  init_continued();
  propagate(start);
  debug_off();
}

References debug_off, debug_on, propagate(), and start.

Referenced by module_name_to_preconditions(), and module_name_to_total_preconditions().

Here is the call graph for this function:

Here is the caller graph for this function:

propagate()

static bool propagate ( statement  s )

static

returns whether propagation is continued after s.

(that is no STOP or infinite loop encountered ??? ). It is a MAY information. If there is no propagation, it is a MUST information.

ifdebug(5) {

pips_debug(1, "Dealing with statement %p\n", s);

print_statement(s);

}

Undecidable implies "propagate" by default

Undecidable implies "propagate" by default

If the unstructured is seen as going on, test if the exit node as been marked as reachable

Since the exit node is not reached, that means that there is an infinite loop is the unstructured, so globally it is not continued:

FI: not satisfying; interprocedural control effects required here

FI: interprocedural exit possible:-(

FI: undone by the controlizer?

Definition at line 124 of file unreachable.c.

                       {
    bool continued = true;
    instruction i;
 
    pips_assert("defined statement", !statement_undefined_p(s));
    /* ifdebug(5) { */
    /*   pips_debug(1, "Dealing with statement %p\n", s); */
    /*   print_statement(s); */
    /* } */
 
    check_recursion(s);
 
    i = statement_instruction(s);
    switch (instruction_tag(i))
    {
    case is_instruction_sequence:
    {
        list l = sequence_statements(instruction_sequence(i));
        while (l && (continued=propagate(STATEMENT(CAR(l)))))
            POP(l);
        break;
    }
    case is_instruction_loop:
    {
        propagate(loop_body(instruction_loop(i)));
        break;
    }
    case is_instruction_whileloop:
    {
        /* Undecidable implies "propagate" by default */
        propagate(whileloop_body(instruction_whileloop(i)));
        break;
    }
    case is_instruction_forloop:
    {
        /* Undecidable implies "propagate" by default */
        propagate(forloop_body(instruction_forloop(i)));
        break;
    }
    case is_instruction_test:
    {
        test t = instruction_test(i);
        bool ctrue, cfalse;
        ctrue = propagate(test_true(t));
        cfalse = propagate(test_false(t));
        continued = ctrue || cfalse;
        break;
    }
    case is_instruction_unstructured:
    {
      unstructured u = instruction_unstructured(i);
      control c = unstructured_control(u);
      // Investigate inside the unstructured control graph:
      continued = control_propagate(c);
      if (continued) {
        /* If the unstructured is seen as going on, test if the exit node
           as been marked as reachable */
        statement exit = control_statement(unstructured_exit(u));
        if (!reached_p(exit))
          /* Since the exit node is not reached, that means that there is
             an infinite loop is the unstructured, so globally it is not
             continued: */
          continued = false;
      }
      break;
    }
    case is_instruction_call:
    {
      /* FI: not satisfying; interprocedural control effects required here */
      entity f = call_function(instruction_call(i));
      continued = !ENTITY_STOP_P(f) && !ENTITY_ABORT_SYSTEM_P(f) && !ENTITY_EXIT_SYSTEM_P(f);
      break;
    }
    case is_instruction_expression:
    {
      continued = true; /* FI: interprocedural exit possible:-( */
      break;
    }
    case is_instruction_multitest:
    {
      pips_internal_error("Not implemented yet"); /* FI: undone by the controlizer? */
      break;
    }
    case is_instruction_goto:
        pips_internal_error("GOTO should have been eliminated by the controlizer");
        break;
    default:
        pips_internal_error("unexpected instruction tag");
    }
 
    pips_debug(1, "Continued for statement %p = %d\n", s, continued);
    store_continued(s, continued);
    return continued;
}

References call_function, CAR, check_recursion, control_propagate(), control_statement, ENTITY_ABORT_SYSTEM_P, ENTITY_EXIT_SYSTEM_P, ENTITY_STOP_P, exit, f(), forloop_body, instruction_call, instruction_forloop, instruction_loop, instruction_sequence, instruction_tag, instruction_test, instruction_unstructured, instruction_whileloop, is_instruction_call, is_instruction_expression, is_instruction_forloop, is_instruction_goto, is_instruction_loop, is_instruction_multitest, is_instruction_sequence, is_instruction_test, is_instruction_unstructured, is_instruction_whileloop, loop_body, pips_assert, pips_debug, pips_internal_error, POP, reached_p, sequence_statements, STATEMENT, statement_instruction, statement_undefined_p, test_false, test_true, unstructured_control, unstructured_exit, and whileloop_body.

Referenced by control_propagate(), and init_reachable().

Here is the call graph for this function:

Here is the caller graph for this function:

statement_continued_p()

bool statement_continued_p

(

statement

s

)

Test if the execution goes on after the given statement.

For example it is false after a "return" in C

Definition at line 242 of file unreachable.c.

{
    if (bound_continued_p(s))
        return continued_p(s);
    else
        return false;
}

References continued_p.

statement_reachable_p()

bool statement_reachable_p

(

statement

s

)

Test if the given statement is reachable from some statements given at init_reachable(start)

Definition at line 234 of file unreachable.c.

{
    return reached_p(s);
}

References reached_p.

Referenced by statement_to_postcondition(), and statement_to_total_precondition().

Here is the caller graph for this function: