unstructured.c File Reference

#include <stdio.h>
#include <string.h>
#include "genC.h"
#include "database.h"
#include "linear.h"
#include "ri.h"
#include "effects.h"
#include "text.h"
#include "text-util.h"
#include "ri-util.h"
#include "effects-util.h"
#include "constants.h"
#include "control.h"
#include "effects-generic.h"
#include "effects-simple.h"
#include "misc.h"
#include "properties.h"
#include "vecteur.h"
#include "contrainte.h"
#include "ray_dte.h"
#include "sommet.h"
#include "sg.h"
#include "polyedre.h"
#include "transformer.h"
#include "semantics.h"

Include dependency graph for unstructured.c:

Go to the source code of this file.

Data Structures
struct	recursive_context

Functions
static void	print_control_node_uns (control c)
	semantical analysis More...
static void	print_control_node_unss_sem (list l)
static transformer	load_control_postcondition (control c, control_mapping control_postcondition_map)
static transformer	load_arc_precondition (control, control, control_mapping)
	forward declaration More...
static transformer	get_control_precondition (control c, control_mapping control_postcondition_map, unstructured u, transformer pre_entry)
static void	store_control_postcondition (control c, transformer post, control_mapping control_postcondition_map)
static void	update_control_postcondition (control c, transformer post, control_mapping control_postcondition_map)
void	print_control_postcondition_map (control_mapping control_postcondition_map)
	unstructured.c More...
static control_mapping	make_control_postcondition_map ()
static control_mapping	free_control_postcondition_map (control_mapping control_postcondition_map)
static transformer	load_control_fix_point (control c, control_mapping control_fix_point_map, hash_table ancestor_map, hash_table scc_map)
	The fix point can be linked either to the entry node of the scc or to the ancestor node. More...
static void	store_control_fix_point (control c, transformer fptf, control_mapping control_fix_point_map)
static control_mapping	make_control_fix_point_map ()
static control_mapping	free_control_fix_point_map (control_mapping control_fix_point_map)
static bool	ready_to_be_processed_p (control c, list to_be_processed, list still_to_be_processed, list already_processed, control_mapping control_postcondition_map)
	a control is ready to be processed if all its predecessors have known postconditions or can receive a trivial empty postcondition More...
transformer	load_cycle_fix_point (control c, hash_table fix_point_map)
static list	unstructured_to_effects (unstructured scc, hash_table ancestor_map, hash_table scc_map)
	In fact, non-deterministic unstructured to effects. More...
static list	non_deterministic_unstructured_to_effects (unstructured scc, hash_table ancestor_map, hash_table scc_map)
static void	process_ready_node (control c, transformer pre_entry, transformer n_pre, unstructured u, control_mapping control_postcondition_map, hash_table ancestor_map, hash_table scc_map, list partition, control_mapping fix_point_map, bool postcondition_p)
static bool	process_unreachable_node (control c, control_mapping control_postcondition_map, bool postcondition_p)
static void	add_cycle_dependency (control d, control c, control_mapping cycle_dependencies_map)
	State that d depends on c: cycle c must be processed before cycle d can be processed. More...
static void	remove_cycle_dependencies (control c, control_mapping cycle_dependencies_map)
	c has been processed and no other cycle can depend on it More...
static list	get_cycle_dependencies (control d, control_mapping cycle_dependencies_map)
	Some cycle may appear nowhere but in the DAG and have no entries in the table. More...
void	update_temporary_precondition (void *k, transformer pre, hash_table precondition_map)
void	update_statement_temporary_precondition (statement s, transformer pre, statement_mapping statement_temporary_precondition_map)
void	print_statement_temporary_precondition (statement_mapping statement_temporary_precondition_map)
void	update_cycle_temporary_precondition (control c, transformer pre, control_mapping cycle_temporary_precondition_map)
transformer	load_cycle_temporary_precondition (control c, control_mapping cycle_temporary_precondition_map, hash_table ancestor_map, hash_table scc_map __attribute__((__unused__)))
transformer	load_statement_temporary_precondition (statement s, statement_mapping statement_temporary_precondition_map)
static void	cycle_to_flow_sensitive_preconditions (list partition, unstructured c_u, hash_table ancestor_map, hash_table scc_map, control_mapping fix_point_map, control_mapping cycle_temporary_precondition_map, statement_mapping statement_temporary_precondition_map, transformer c_pre, transformer pre, control_mapping control_postcondition_map)
	Very likely the transformer paths wrt the entry point and not really a postcondition. More...
static void	dag_to_flow_sensitive_preconditions (list partition, unstructured ndu, hash_table ancestor_map, hash_table scc_map, control_mapping fix_point_map, transformer pre_u, transformer pre, control_mapping control_postcondition_map)
transformer	dag_or_cycle_to_flow_sensitive_postconditions_or_transformers (list partition, unstructured ndu, hash_table ancestor_map, hash_table scc_map, control_mapping fix_point_map, transformer e_pre, transformer n_pre, hash_table control_postcondition_map, bool postcondition_p, bool is_dag)
	Should ndu be a dag or a cycle? More...
transformer	dag_to_flow_sensitive_postconditions_or_transformers (list partition, unstructured ndu, hash_table ancestor_map, hash_table scc_map, control_mapping fix_point_map, transformer e_pre, transformer n_pre, hash_table control_postcondition_map, bool postcondition_p)
	Compute transformers or preconditions. More...
transformer	cycle_to_flow_sensitive_postconditions_or_transformers (list partition, unstructured ndu, hash_table ancestor_map, hash_table scc_map, control_mapping fix_point_map, transformer e_pre, transformer n_pre, hash_table control_postcondition_map, bool postcondition_p)
	Compute transformers or preconditions. More...
static void	local_process_unreachable_node (control c, recursive_context *pcontext)
static void	node_to_path_transformer_or_postcondition (control c, recursive_context *pcontext)
	A debug function to prettyprint the result. More...
static void	print_cycle_head_to_fixpoint (control c, recursive_context *pcontext)
	A debug function to prettyprint the fix points. More...
transformer	unstructured_to_flow_sensitive_postconditions_or_transformers (transformer pre_u, transformer pre, unstructured u, bool postcondition_p)
	compute either the postconditions in an unstructured or the transformer of this unstructured. More...
static transformer	unstructured_to_postconditions (transformer pre, transformer pre_first, unstructured u)
transformer	unstructured_to_flow_sensitive_postconditions (transformer pre_u, transformer pre, unstructured u)
	compute pre- and post-conditions in an unstructured from the entry precondition pre and return the exit postcondition. More...
transformer	unstructured_to_postcondition (transformer pre, unstructured u, transformer tf)
static void	unreachable_node_to_transformer (control c)
transformer	unstructured_to_flow_insensitive_transformer (unstructured u)
	This simple fix-point over-approximates the CFG by a fully connected graph. More...
static void	unstructured_to_transformers (unstructured u, transformer pre)
	Computation of transformers associated to each node of u and to each of its sub-statements. More...
transformer	unstructured_to_transformer (unstructured u, transformer e_pre, list e)
	effects of u More...
transformer	unstructured_to_flow_sensitive_total_preconditions (transformer t_post_u, transformer pre, unstructured u)

Function Documentation

add_cycle_dependency()

static void add_cycle_dependency ( control  d, control  c, control_mapping  cycle_dependencies_map  )

static

State that d depends on c: cycle c must be processed before cycle d can be processed.

Update the hash_table by side effect

Definition at line 934 of file unstructured.c.

{
  list dependencies = (list) hash_get((hash_table) cycle_dependencies_map,
                                      (void *) d);
 
  if(dependencies == (list) HASH_UNDEFINED_VALUE) {
    dependencies = CONS(CONTROL, c, NIL);
    hash_put((hash_table) (cycle_dependencies_map),
           (void *) d, (void *) dependencies);
  }
  else {
    /* Update the hash_table by side effect */
    dependencies = gen_nconc(dependencies, CONS(CONTROL, c, NIL));
  }
}

References CONS, CONTROL, gen_nconc(), hash_get(), hash_put(), HASH_UNDEFINED_VALUE, and NIL.

Referenced by dag_to_flow_sensitive_preconditions().

Here is the call graph for this function:

Here is the caller graph for this function:

cycle_to_flow_sensitive_postconditions_or_transformers()

transformer cycle_to_flow_sensitive_postconditions_or_transformers	(	list	partition,
		unstructured	ndu,
		hash_table	ancestor_map,
		hash_table	scc_map,
		control_mapping	fix_point_map,
		transformer	e_pre,
		transformer	n_pre,
		hash_table	control_postcondition_map,
		bool	postcondition_p
	)

Compute transformers or preconditions.

Parameters

partition	artition
ndu	Bourdoncle's processing ordering
ancestor_map	A non-deterministic acyclic control flow graph
scc_map	Mapping from non-deterministic nodes to deterministic nodes
fix_point_map	mapping from deterministic nodes to non-deterministic cycles
e_pre	mapping from cycle heads to fix point transformers
n_pre	precondition on entry
control_postcondition_map	precondition true for any node.
postcondition_p	ostcondition_p

Definition at line 1744 of file unstructured.c.

{
  transformer tf = transformer_undefined;
 
  tf = dag_or_cycle_to_flow_sensitive_postconditions_or_transformers
    (partition, ndu, ancestor_map, scc_map, fix_point_map, e_pre, n_pre,
     control_postcondition_map, postcondition_p, false);
 
  return tf;
}

References dag_or_cycle_to_flow_sensitive_postconditions_or_transformers(), and transformer_undefined.

Referenced by process_ready_node().

Here is the call graph for this function:

Here is the caller graph for this function:

cycle_to_flow_sensitive_preconditions()

static void cycle_to_flow_sensitive_preconditions ( list  partition, unstructured  c_u, hash_table  ancestor_map, hash_table  scc_map, control_mapping  fix_point_map, control_mapping  cycle_temporary_precondition_map, statement_mapping  statement_temporary_precondition_map, transformer  c_pre, transformer  pre, control_mapping  control_postcondition_map  )

static

Very likely the transformer paths wrt the entry point and not really a postcondition.

Let's update it as a real postcondition.

Yet another forward DAG propagation with an exception for the cycle head: cut-and-paste and adapt

forward reachable nodes in u

FI: Please the compiler complaining about useless parameters (and remove them later!)

wide_forward_control_map_get_blocs(unstructured_control(u), &to_be_processed);

Take care of the entry node whose precondition does not rely on its predecessors

post = statement_to_postcondition(c_pre, es);

c_pre is USED

Propagate the postcondition downwards

process forward

right away because c's cdr might be modified

Already done earlier if(cycle_head_p(c, ancestor_map, scc_map)) { transformer fp_tf = load_control_fix_point(a, fix_point_map, ancestor_map, scc_map); e_pre = transformer_apply(fp_tf, pre); update_cycle_temporary_precondition (a, e_pre, cycle_temporary_precondition_map); } else { e_pre = transformer_dup(pre); }

fix point are unique for all replication of a cycle

(a, e_pre, cycle_temporary_precondition_map);

Go down the subcycle... when necessary... since there is a loop somewhere else and the cycles are called in the right order?

post = statement_to_postcondition(transformer_dup(e_pre), c_s);

FI: you should use the really current precondition using load_statement_temporary_precondition()

post = transformer_apply(load_statement_transformer(c_s), e_pre);

Hard to track memory leaks...

It is much too late to update the control postcondition!

update_control_postcondition(c, post, control_postcondition_map);

FI: just to see what happens, without any understanding of the process

FI: what is the point when control are replicated?

The precondition for the entry node may be improved by now using the precondition of its predecessors and the cycle entry. OK, but to what end?

Parameters

c_u	Is it relevant?
ancestor_map	The cycle unstructured
statement_temporary_precondition_map	To be updated when a cycle head is encountered
c_pre	To be updated each time a statement is encountered
pre	precondition of cycle c_u, already processed with the fix point
control_postcondition_map	aproximate precondition holding for all nodes

Definition at line 1080 of file unstructured.c.

{
  /* Yet another forward DAG propagation with an exception for the cycle
     head: cut-and-paste and adapt */
  list to_be_processed = NIL; /* forward reachable nodes in u */
  list still_to_be_processed = NIL;
  list already_processed = NIL;
  control e = unstructured_control(c_u);
  statement es = control_statement(e);
  transformer post = transformer_undefined;
 
  /* FI: Please the compiler complaining about useless parameters (and
     remove them later!) */
  pips_assert("Please the compiler", partition==partition);
  pips_assert("Please the compiler",
              cycle_temporary_precondition_map==cycle_temporary_precondition_map);
  pips_assert("Please the compiler", pre==pre);
 
  /* wide_forward_control_map_get_blocs(unstructured_control(u), &to_be_processed); */
  forward_control_map_get_blocs(unstructured_control(c_u), &to_be_processed);
  still_to_be_processed = gen_copy_seq(to_be_processed);
 
  /* Take care of the entry node whose precondition does not rely on its
     predecessors */
  /* post = statement_to_postcondition(c_pre, es); */ /* c_pre is USED */
  post = transformer_apply(load_statement_transformer(es), c_pre);
  update_control_postcondition(e, post, control_postcondition_map);
  gen_remove(&still_to_be_processed, e);
  already_processed = CONS(CONTROL, e, NIL);
 
  /* Propagate the postcondition downwards */
 
  while(!ENDP(still_to_be_processed)) {
    int count = -1;
    do {
      list l = list_undefined;
 
      /* process forward */
      pips_debug(5, "Try forward processing for\n");
      ifdebug(5) print_control_node_unss_sem(still_to_be_processed);
 
      count = 0;
      for(l=still_to_be_processed; !ENDP(l); ) {
        control c = CONTROL(CAR(l));
        POP(l); /* right away because c's cdr might be modified */
        if(meaningless_control_p(c)
           || ready_to_be_processed_p(c, to_be_processed,
                                      still_to_be_processed,
                                      already_processed,
                                      control_postcondition_map)) {
          if(!meaningless_control_p(c)) {
            control c_a = control_undefined;
            /*
            process_ready_node(c, n_pre, n_pre, ndu, control_postcondition_map,
                               ancestor_map, scc_map, partition, fix_point_map, postcondition_p);
            */
            statement c_s = control_statement(c);
            transformer pre =
              get_control_precondition(c, control_postcondition_map, c_u, c_pre);
            transformer e_pre = transformer_undefined;
            transformer f_e_pre = transformer_undefined;
            transformer c_e_pre = transformer_undefined;
 
            /* Already done earlier
            if(cycle_head_p(c, ancestor_map, scc_map)) {
              transformer fp_tf =  load_control_fix_point(a, fix_point_map, ancestor_map, scc_map);
              e_pre = transformer_apply(fp_tf, pre);
              update_cycle_temporary_precondition
                (a, e_pre, cycle_temporary_precondition_map);
            }
            else {
              e_pre = transformer_dup(pre);
            }
            */
            e_pre = transformer_dup(pre);
            if(cycle_head_p(c, ancestor_map, scc_map)) {
              unstructured sub_scc = unstructured_undefined;
              /*
              transformer n_pre = transformer_undefined;
              transformer t_sub_scc = transformer_undefined;
              */
 
              if(!get_bool_property("SEMANTICS_COMPUTE_TRANSFORMERS_IN_CONTEXT")) {
              /* fix point are unique for all replication of a cycle */
                c_a = control_to_ancestor(c, ancestor_map);
                sub_scc = ancestor_cycle_head_to_scc(c_a, scc_map);
              }
              else {
                sub_scc = ancestor_cycle_head_to_scc(c, scc_map);
                c_a = unstructured_control(sub_scc);
              }
 
              update_cycle_temporary_precondition
                (c_a, e_pre, cycle_temporary_precondition_map);
              /* (a, e_pre, cycle_temporary_precondition_map); */
 
              /* Go down the subcycle... when necessary... since there is a loop somewhere else and the cycles are called in the right order? */
              /*
              cycle_to_flow_sensitive_preconditions
                (partition, sub_scc, ancestor_map, scc_map, fix_point_map,
                 cycle_temporary_precondition_map, statement_temporary_precondition_map,
                 e_pre, n_pre, control_postcondition_map);
              */
            }
            update_statement_temporary_precondition
              (c_s, e_pre, statement_temporary_precondition_map);
            /* post = statement_to_postcondition(transformer_dup(e_pre), c_s); */
            /* FI: you should use the really current precondition using
               load_statement_temporary_precondition() */
            /* post = transformer_apply(load_statement_transformer(c_s), e_pre); */
            /* Hard to track memory leaks... */
            /* It is much too late to update the control postcondition! */
            /* update_control_postcondition(c, post, control_postcondition_map); */
            /* FI: just to see what happens, without any understanding of the process */
            f_e_pre = load_statement_temporary_precondition(c_s,
                                                            statement_temporary_precondition_map);
            if(cycle_head_p(c, ancestor_map, scc_map)) {
              transformer ctf = load_control_fix_point(c, fix_point_map,
                                                       ancestor_map, scc_map);
              c_e_pre = transformer_apply(ctf, f_e_pre);
            }
            else {
              c_e_pre = transformer_dup(f_e_pre);
            }
            post = transformer_apply(load_statement_transformer(c_s), c_e_pre);
            /* FI: what is the point when control are replicated? */
            update_control_postcondition(c, post, control_postcondition_map);
            free_transformer(c_e_pre);
          }
          gen_remove(&still_to_be_processed, c);
          already_processed = gen_append(already_processed, CONS(CONTROL, c, NIL));
          count++;
        }
      }
    } while(count!=0);
    if(!ENDP(still_to_be_processed)) {
      pips_assert("still_to_be_processed is empty because of the Bourdoncle's restructuring",
                  false);
    }
  }
  /* The precondition for the entry node may be improved by now using the
     precondition of its predecessors and the cycle entry. OK, but to what end? */
}

References ancestor_cycle_head_to_scc(), CAR, CONS, CONTROL, control_statement, control_to_ancestor(), control_undefined, count, cycle_head_p(), ENDP, forward_control_map_get_blocs(), free_transformer(), gen_append(), gen_copy_seq(), gen_remove(), get_bool_property(), get_control_precondition(), ifdebug, list_undefined, load_control_fix_point(), load_statement_temporary_precondition(), load_statement_transformer(), meaningless_control_p(), NIL, pips_assert, pips_debug, POP, print_control_node_unss_sem(), ready_to_be_processed_p(), transformer_apply(), transformer_dup(), transformer_undefined, unstructured_control, unstructured_undefined, update_control_postcondition(), update_cycle_temporary_precondition(), and update_statement_temporary_precondition().

Referenced by dag_to_flow_sensitive_preconditions().

Here is the call graph for this function:

Here is the caller graph for this function:

dag_or_cycle_to_flow_sensitive_postconditions_or_transformers()

transformer dag_or_cycle_to_flow_sensitive_postconditions_or_transformers	(	list	partition,
		unstructured	ndu,
		hash_table	ancestor_map,
		hash_table	scc_map,
		control_mapping	fix_point_map,
		transformer	e_pre,
		transformer	n_pre,
		hash_table	control_postcondition_map,
		bool	postcondition_p,
		bool	is_dag
	)

Should ndu be a dag or a cycle?

forward reachable nodes in u

The whole business could be simplified by using a larger definition of "to_be_processed".

wide_forward_control_map_get_blocs(unstructured_control(u), &to_be_processed);

Take care of unreachable nodes

FI: Wouldn't it be better to clean up the unstructured? Aren't they supposed to be clean? This piece of code contradict get_control_precondition() where the problem could be fixed at a lower cost. Another place where the problem is handled is ready_to_be_processed_p(), but it is called on still_to_be_processed, which does not take into account unreachable nodes. To make things worse, the daVinci printouts only include, most of the time, only reachable nodes.

Take care of the entry node

The entry node must be handled in a specific way... but not in the specific way implemented in process_ready_node() which only deals with DAG's. The entry node cannot be a meaningless control node.

Since control nodes have been replicated, it is difficult to predict if es has already been processed or not.

make_control_postcondition_map();

Take care of the forward reachable control nodes

process forward

right away because c's cdr might be modified

Compute fix point transformer for cycle

Compute the convex hull of the paths associated to each predecessor of the entry. Since this is a cycle, preds cannot be empty.

transformer fp_tf_plus = transformer_undefined;

If an entry range is known, do not use it as there may be more than one occurence of the cycle and more than one entry range. Keep this refinement to the precondition computation phase? It might be too late. The the data structure should be change to store more than one fix point per cycle.

Not convincing anyway: you should apply fp_tf_plus to e_pre for the next two lines to make sense.

Use the + fix point to preserve more information about the output and do not forget to perform a convex hull when you need a * fix point in process_ready_node()

Instead of computing the convex hull over all paths before computing the fix point, compute the fix point of a list of transformers.

e may have many synonyms

fix point are unique for all replication of a cycle

each cycle replication has its own fix-point

We might want to return the corresponding fix point?

Parameters

partition	artition
ndu	Bourdoncle's processing ordering
ancestor_map	A non-deterministic acyclic control flow graph
scc_map	Mapping from non-deterministic nodes to deterministic nodes
fix_point_map	mapping from deterministic nodes to non-deterministic cycles
e_pre	mapping from cycle heads to fix point transformers
n_pre	precondition on entry
control_postcondition_map	precondition true for any node.
postcondition_p	ostcondition_p
is_dag	Compute transformers or preconditions

Definition at line 1509 of file unstructured.c.

{
  transformer tf = transformer_undefined;
  list to_be_processed = NIL; /* forward reachable nodes in u */
  list still_to_be_processed = NIL;
  list already_processed = NIL;
  list cannot_be_reached = NIL;
 
  ifdebug(2) {
    pips_debug(2, "Begin for unstructured %p with e_pre=%p:\n", ndu, e_pre);
    print_transformer(e_pre);
  }
 
  /* The whole business could be simplified by using a larger definition of "to_be_processed". */
  /* wide_forward_control_map_get_blocs(unstructured_control(u), &to_be_processed); */
  forward_control_map_get_blocs(unstructured_control(ndu), &to_be_processed);
  control_map_get_blocs(unstructured_control(ndu), &cannot_be_reached);
  still_to_be_processed = gen_copy_seq(to_be_processed);
  gen_list_and_not(&cannot_be_reached, to_be_processed);
 
  /* Take care of unreachable nodes */
 
  if(!ENDP(cannot_be_reached)) {
    /* FI: Wouldn't it be better to clean up the unstructured? Aren't they
       supposed to be clean? This piece of code contradict
       get_control_precondition() where the problem could be fixed at a
       lower cost. Another place where the problem is handled is
       ready_to_be_processed_p(), but it is called on
       still_to_be_processed, which does not take into account unreachable
       nodes. To make things worse, the daVinci printouts only include,
       most of the time, only reachable nodes. */
    ifdebug(3) {
      pips_debug(3, "Process unreachable nodes in unstructured %p\n", ndu);
      print_control_node_unss_sem(cannot_be_reached);
    }
    MAP(CONTROL, cbrc, {
      if(!meaningless_control_p(cbrc)) {
        transformer etf = transformer_empty();
        store_control_postcondition(cbrc, etf, control_postcondition_map);
      }
    }, cannot_be_reached);
    gen_free_list(cannot_be_reached);
    cannot_be_reached = list_undefined;
  }
 
  pips_assert("Node lists are defined", !list_undefined_p(to_be_processed)
              && !list_undefined_p(still_to_be_processed) && ENDP(already_processed) );
 
  /* Take care of the entry node */
 
  if(!is_dag && !postcondition_p) {
    /* The entry node must be handled in a specific way... but not in the
       specific way implemented in process_ready_node() which only deals
       with DAG's. The entry node cannot be a meaningless control node. */
    control e = unstructured_control(ndu);
    statement es = control_statement(e);
    transformer etf = load_statement_transformer(es);
    transformer init = transformer_identity();
    transformer post = transformer_undefined;
 
    /* Since control nodes have been replicated, it is difficult to
       predict if es has already been processed or not. */
    if(transformer_undefined_p(etf)) {
      etf = statement_to_transformer(es, n_pre);
    }
 
    post = transformer_apply(etf, init);
 
    store_control_postcondition(e, post, control_postcondition_map);
 
    gen_remove(&still_to_be_processed, e);
    already_processed = CONS(CONTROL, e, NIL);
  }
 
  /* make_control_postcondition_map(); */
 
  /* Take care of the forward reachable control nodes */
 
  while(!ENDP(still_to_be_processed)) {
    int count = -1;
    do {
      list l = list_undefined;
 
      /* process forward */
      pips_debug(5, "Try forward processing for\n");
      ifdebug(2) print_control_node_unss_sem(still_to_be_processed);
 
      count = 0;
      for(l=still_to_be_processed; !ENDP(l); ) {
        control c = CONTROL(CAR(l));
        POP(l); /* right away because c's cdr might be modified */
        if(meaningless_control_p(c)
           || ready_to_be_processed_p(c, to_be_processed,
                                      still_to_be_processed,
                                      already_processed,
                                      control_postcondition_map)) {
          if(!meaningless_control_p(c)) {
            process_ready_node(c, e_pre, n_pre, ndu, control_postcondition_map,
                               ancestor_map, scc_map, partition, fix_point_map, postcondition_p);
          }
          gen_remove(&still_to_be_processed, c);
          already_processed = gen_append(already_processed, CONS(CONTROL, c, NIL));
          count++;
        }
      }
    } while(count!=0);
    if(!ENDP(still_to_be_processed)) {
      pips_assert("still_to_be_processed is empty because of the Bourdoncle's restructuring",
                  false);
    }
  }
 
  /* Compute fix point transformer for cycle */
  if(!is_dag && !postcondition_p) {
    transformer fp_tf = transformer_undefined;
    control e = unstructured_control(ndu);
    list preds = control_predecessors(e);
    control e_a = control_undefined;
    // FI: we also need SEMANTICS_USE_DERIVATIVE_LIST = TRUE
    // but this should be soon the default option
    if(!get_bool_property("SEMANTICS_USE_TRANSFORMER_LISTS")) {
      /* Compute the convex hull of the paths associated to each predecessor
         of the entry. Since this is a cycle, preds cannot be empty. */
      control pred = CONTROL(CAR(preds));
      transformer path_tf =
        load_arc_precondition(pred, e, control_postcondition_map);
      /* transformer fp_tf_plus = transformer_undefined; */
 
      POP(preds);
      FOREACH(CONTROL, pred, preds) {
        transformer pred_tf =
          load_arc_precondition(pred, e, control_postcondition_map);
        transformer old_path_tf = path_tf;
 
        pips_assert("Partial path transformer pred_tf is defined",
                    !transformer_undefined_p(pred_tf));
        path_tf = transformer_convex_hull(old_path_tf, pred_tf);
        free_transformer(old_path_tf);
      }
 
      fp_tf =  (*transformer_fix_point_operator)(path_tf);
      /* If an entry range is known, do not use it as there may be more than
         one occurence of the cycle and more than one entry range. Keep this
         refinement to the precondition computation phase? It might be too
         late. The the data structure should be change to store more than
         one fix point per cycle.  */
      /* Not convincing anyway: you should apply fp_tf_plus to e_pre for the
         next two lines to make sense. */
      /* Use the + fix point to preserve more information about the output
         and do not forget to perform a convex hull when you need a * fix
         point in process_ready_node() */
      fp_tf = transformer_combine(fp_tf, path_tf);
      /*
        fp_tf = transformer_convex_hull(fp_tf_plus, e_pre);
      */
      free_transformer(path_tf);
    }
    else {
      /* Instead of computing the convex hull over all paths before
         computing the fix point, compute the fix point of a list of
         transformers. */
      list tl = NIL;
      FOREACH(CONTROL, pred, preds) {
        transformer pred_tf =
          load_arc_precondition(pred, e, control_postcondition_map);
        tl = CONS(TRANSFORMER, pred_tf, tl);
      }
      fp_tf = transformer_list_transitive_closure_plus(tl);
      gen_free_list(tl);
    }
 
    /* e may have many synonyms */
 
    if(!get_bool_property("SEMANTICS_COMPUTE_TRANSFORMERS_IN_CONTEXT")) {
      /* fix point are unique for all replication of a cycle */
      e_a = control_to_ancestor(e, ancestor_map);
    }
    else {
      /* each cycle replication has its own fix-point */
      e_a = e;
    }
    store_control_fix_point(e_a, fp_tf, fix_point_map);
 
    /* We might want to return the corresponding fix point? */
    tf = fp_tf;
  }
 
  gen_free_list(to_be_processed);
  to_be_processed = list_undefined;
  gen_free_list(still_to_be_processed);
  still_to_be_processed = list_undefined;
  gen_free_list(already_processed);
  already_processed = list_undefined;
 
  ifdebug(2) {
    pips_debug(2, "End for %s of %s %p with entry node %s and with transformer %p\n",
               postcondition_p? "postcondition" : "transformer",
               is_dag? "dag" : "cycle", ndu,
               statement_identification(control_statement(unstructured_control(ndu))), tf);
    print_transformer(tf);
  }
 
  return tf;
}

References CAR, CONS, CONTROL, control_map_get_blocs(), control_predecessors, control_statement, control_to_ancestor(), control_undefined, count, ENDP, FOREACH, forward_control_map_get_blocs(), free_transformer(), gen_append(), gen_copy_seq(), gen_free_list(), gen_list_and_not(), gen_remove(), get_bool_property(), ifdebug, init, list_undefined, list_undefined_p, load_arc_precondition(), load_statement_transformer(), MAP, meaningless_control_p(), NIL, pips_assert, pips_debug, POP, print_control_node_unss_sem(), print_transformer, process_ready_node(), ready_to_be_processed_p(), statement_identification(), statement_to_transformer(), store_control_fix_point(), store_control_postcondition(), TRANSFORMER, transformer_apply(), transformer_combine(), transformer_convex_hull(), transformer_empty(), transformer_identity(), transformer_list_transitive_closure_plus(), transformer_undefined, transformer_undefined_p, and unstructured_control.

Referenced by cycle_to_flow_sensitive_postconditions_or_transformers(), and dag_to_flow_sensitive_postconditions_or_transformers().

Here is the call graph for this function:

Here is the caller graph for this function:

dag_to_flow_sensitive_postconditions_or_transformers()

transformer dag_to_flow_sensitive_postconditions_or_transformers	(	list	partition,
		unstructured	ndu,
		hash_table	ancestor_map,
		hash_table	scc_map,
		control_mapping	fix_point_map,
		transformer	e_pre,
		transformer	n_pre,
		hash_table	control_postcondition_map,
		bool	postcondition_p
	)

Compute transformers or preconditions.

Parameters

partition	artition
ndu	Bourdoncle's processing ordering
ancestor_map	A non-deterministic acyclic control flow graph
scc_map	Mapping from non-deterministic nodes to deterministic nodes
fix_point_map	mapping from deterministic nodes to non-deterministic cycles
e_pre	mapping from cycle heads to fix point transformers
n_pre	precondition on entry
control_postcondition_map	precondition true for any node.
postcondition_p	ostcondition_p

Definition at line 1724 of file unstructured.c.

{
  transformer tf = transformer_undefined;
 
  tf = dag_or_cycle_to_flow_sensitive_postconditions_or_transformers
    (partition, ndu, ancestor_map, scc_map, fix_point_map, e_pre, n_pre,
     control_postcondition_map, postcondition_p, true);
 
  return tf;
}

References dag_or_cycle_to_flow_sensitive_postconditions_or_transformers(), and transformer_undefined.

Referenced by unstructured_to_flow_sensitive_postconditions_or_transformers().

Here is the call graph for this function:

Here is the caller graph for this function:

dag_to_flow_sensitive_preconditions()

static void dag_to_flow_sensitive_preconditions ( list  partition, unstructured  ndu, hash_table  ancestor_map, hash_table  scc_map, control_mapping  fix_point_map, transformer  pre_u, transformer  pre, control_mapping  control_postcondition_map  )

static

A statement may appear in several nodes, and the same is true for cycles.

DUPLICATED CODE

The cycle is entered

Or the cycle is not entered and the store is not in fptf's domain.

Have we followed a true or a false branch? We'll know later but it is better to add this information before the convex hull is performed.

FI: I do not know why an empty context is passed down.

free_transformer(pre);

END OF DUPLICATED CODE

e_pre = transformer_apply(fp_tf, pre);

fix point are unique for all replication of a cycle

update_cycle_temporary_precondition(a, e_pre, cycle_temporary_precondition_map);

FI: sharing between statement_temporary_precondition and statement_temporary_precondition; freeing the second one frees part of the first one

Build the cycle dependencies

control a = control_to_ancestor(c, ancestor_map);

unstructured scc_ u = cycle_head_to_scc(c, ancestor_map, scc_map);

build dependencies among ancestors, which are representative of scc's

then cc depends on c

build dependencies among heads, which are representative of scc's

No cycles with dependencies

While some cycles still have to be processed.

right away because c's cdr might be modified

The precondition of cycle c is complete

control a = control_to_ancestor(c, ancestor_map);

Definition at line 1234 of file unstructured.c.

{
  /* A statement may appear in several nodes, and the same is true for cycles. */
  statement_mapping statement_temporary_precondition_map = MAKE_STATEMENT_MAPPING();
  control_mapping cycle_temporary_precondition_map = MAKE_CONTROL_MAPPING();
  control_mapping cycle_dependencies_map = MAKE_CONTROL_MAPPING();
  list still_to_be_processed = NIL;
  list already_processed = NIL;
  control e = unstructured_control(ndu);
  list nl = NIL;
  list c_c = list_undefined;
 
  ifdebug(2) {
    pips_debug(2, "Begin with control_postcondition_map=%p:\n",
               control_postcondition_map);
    print_control_postcondition_map(control_postcondition_map);
  }
 
  /*
   * Process first the nodes in the embedding graph, in any order since
   * node postconditions are assumed available.
   *
   */
  control_map_get_blocs(e, &nl);
 
  for(c_c = nl; !ENDP(c_c); POP(c_c)) {
    control c = CONTROL(CAR(c_c));
 
    if(!meaningless_control_p(c)) {
      control c_a = control_undefined;
      transformer pre = get_control_precondition(c, control_postcondition_map, ndu, pre_u);
      transformer e_pre = transformer_undefined;
      statement s = control_statement(c);
 
      if(cycle_head_p(c, ancestor_map, scc_map)) {
        transformer fp_tf = load_control_fix_point(c, fix_point_map, ancestor_map, scc_map);
 
        /* DUPLICATED CODE */
 
        /* The cycle is entered */
        transformer pre_cycle = transformer_apply(fp_tf, pre);
        /* Or the cycle is not entered and the store is not in fptf's domain. */
        transformer pre_no_cycle = transformer_dup(pre);
        if(control_test_p(c)) {
          /* Have we followed a true or a false branch? We'll know later but
             it is better to add this information before the convex hull is
             performed. */
          statement stmt = control_statement(c);
          expression e = test_condition(statement_test(stmt));
 
          /* FI: I do not know why an empty context is passed down. */
          if(true_successors_only_p(c)) {
            pre_no_cycle = precondition_add_condition_information(pre_no_cycle, e,
                                                                  transformer_undefined, true);
          }
          else if(false_successors_only_p(c)) {
            pre_no_cycle = precondition_add_condition_information(pre_no_cycle, e,
                                                                  transformer_undefined, false);
          }
        }
        /* free_transformer(pre); */
        e_pre = transformer_convex_hull(pre_cycle, pre_no_cycle);
        free_transformer(pre_cycle);
        free_transformer(pre_no_cycle);
 
        /* END OF DUPLICATED CODE */
 
        /* e_pre = transformer_apply(fp_tf, pre); */
 
        if(!get_bool_property("SEMANTICS_COMPUTE_TRANSFORMERS_IN_CONTEXT")) {
          /* fix point are unique for all replication of a cycle */
          c_a = control_to_ancestor(c, ancestor_map);
        }
        else {
          c_a = unstructured_control(ancestor_cycle_head_to_scc(c, scc_map));
        }
        update_cycle_temporary_precondition(c_a, e_pre, cycle_temporary_precondition_map);
        /* update_cycle_temporary_precondition(a, e_pre, cycle_temporary_precondition_map); */
      }
      else {
        e_pre = transformer_dup(pre);
      }
      /* FI: sharing between statement_temporary_precondition and
         statement_temporary_precondition; freeing the second one frees
         part of the first one */
      update_statement_temporary_precondition(s, e_pre, statement_temporary_precondition_map);
    }
  }
 
  gen_free_list(nl);
 
  ifdebug(2) {
    pips_debug(2, "\nPreconditions for statements after ND DAG processing:\n");
    print_statement_temporary_precondition(statement_temporary_precondition_map);
    pips_debug(2, "End of preconditions for statements after ND DAG processing:\n\n");
  }
 
  /*
   * Process the cycles from top to bottom in width first?
   * Let's use the partition generated by Bourdoncle?!?
   *
   * Since cycles are not duplicated when transformers are not computed in
   * context, the preconditions of all their instances must be unioned
   * before preconditions can be propagated down in the cycles. When
   * cycles are replicated to have one cycle per cycle call site, the same
   * scheme can be used, as long as dependencies are properly computed.
   *
   * Each cycle c depends on a list of cycles, each of these containing a
   * cycle call site to c.
   *
   * When cycles are not replicated, the dependencies are based on the
   * ancestor of the head, so as to have a unique representative. When
   * cycles are replicated according to cycle call sites, the dependencies
   * are based on the head of the cycle.
   *
   * It is not clear than a topological order exists. Assume that C2
   * occurs in an entry path to C1 and within C1. Somehow the precise
   * precondition of C1 depends on C2's postcondition which depends on
   * C2's precondition. C2's precondition depends on C1's postcondition
   * which depends on C1's precondition and here is the loop.
   *
   * However, in the previous case, the first instance of C2 can be dealt
   * with its transformer and the precondition of its first instance.
   *
   * */
 
  /* Build the cycle dependencies */
  pips_debug(2, "Compute dependencies for %d cycle%s\n",
             hash_table_entry_count(scc_map),
             hash_table_entry_count(scc_map)>1? "s":"");
  HASH_MAP(c, cndu, {
    /* control a = control_to_ancestor(c, ancestor_map); */
    /* unstructured scc_ u = cycle_head_to_scc(c, ancestor_map, scc_map); */
    list nl = NIL;
    list c_cc = list_undefined;
    control head = unstructured_control((unstructured) cndu);
    statement hs = control_statement(head);
 
    pips_debug(8, "Compute dependencies for cycle %p with statement %s\n",
               head, statement_identification(hs));
 
    control_map_get_blocs(head, &nl);
 
    for(c_cc=nl; !ENDP(c_cc); POP(c_cc)) {
      control cc = CONTROL(CAR(c_cc));
 
      if(!meaningless_control_p(cc)
         && cycle_head_p(cc, ancestor_map, scc_map)) {
        if(!get_bool_property("SEMANTICS_COMPUTE_TRANSFORMERS_IN_CONTEXT")) {
          /* build dependencies among ancestors, which are representative of scc's */
          control aa = control_to_ancestor(cc, ancestor_map);
          if(aa!=c) {
            /* then cc depends on c */
            add_cycle_dependency(aa, (control) c, cycle_dependencies_map);
          }
        }
        else {
          /* build dependencies among heads, which are representative of scc's */
          unstructured scc_u = ancestor_cycle_head_to_scc(cc, scc_map);
          control head_scc = unstructured_control(scc_u);
          if(head_scc!=(control)c) {
            add_cycle_dependency(head_scc, head, cycle_dependencies_map);
          }
        }
      }
    }
 
    if(!get_bool_property("SEMANTICS_COMPUTE_TRANSFORMERS_IN_CONTEXT")) {
      still_to_be_processed = CONS(CONTROL, (control) c, still_to_be_processed);
    }
    else {
      still_to_be_processed = CONS(CONTROL, head, still_to_be_processed);
    }
    gen_free_list(nl);
  }, scc_map);
 
  ifdebug(2) {
    if(hash_table_entry_count(cycle_dependencies_map)>0) {
      pips_debug(2, "cycle dependencies:\n");
      HASH_MAP(c, l, {
        statement s = control_statement((control) c);
        pips_debug(2, "Cycle %p with statement %s depends on:\n",
                   c, statement_identification(s));
        print_control_node_unss_sem((list) l);
      }, cycle_dependencies_map);
    }
    else {
      /* No cycles with dependencies */
      pips_debug(2, "no cycles with dependencies\n");
    }
  }
 
  /* While some cycles still have to be processed. */
  while(!ENDP(still_to_be_processed)) {
    int count = -1;
    do {
      list l = list_undefined;
      count = 0;
      for(l=still_to_be_processed; !ENDP(l); ) {
        control c = CONTROL(CAR(l));
 
        list dep = get_cycle_dependencies(c, cycle_dependencies_map);
        POP(l); /* right away because c's cdr might be modified */
 
        ifdebug(8) {
          if(ENDP(dep)) {
            pips_debug(8, "Process cycle %p with statement %s\n",
                       c, statement_identification(control_statement(c)));
          }
        }
 
        if(ENDP(dep)) {
          /* The precondition of cycle c is complete */
          /* control a = control_to_ancestor(c, ancestor_map); */
          transformer c_pre = load_cycle_temporary_precondition(c,
                                                                cycle_temporary_precondition_map,
                                                                ancestor_map, scc_map);
          transformer fp_tf = load_control_fix_point(c, fix_point_map, ancestor_map, scc_map);
          unstructured c_u = unstructured_undefined;
          transformer f_c_pre = transformer_apply(fp_tf, c_pre);
          transformer e_c_pre = transformer_convex_hull(f_c_pre, c_pre);
 
          if(!get_bool_property("SEMANTICS_COMPUTE_TRANSFORMERS_IN_CONTEXT"))
            c_u = cycle_head_to_scc(c, ancestor_map, scc_map);
          else
            c_u = proper_cycle_head_to_scc(c, scc_map);
 
          cycle_to_flow_sensitive_preconditions
            (partition, c_u, ancestor_map, scc_map, fix_point_map,
             cycle_temporary_precondition_map, statement_temporary_precondition_map,
             e_c_pre, pre, control_postcondition_map);
          remove_cycle_dependencies(c, cycle_dependencies_map);
          gen_remove(&still_to_be_processed, c);
          already_processed = gen_append(already_processed, CONS(CONTROL, c, NIL));
          count++;
        }
      }
    } while(count!=0);
 
    pips_assert("All cycles have been processed",
                ENDP(still_to_be_processed));
  }
 
  /*
   * Exploit the temporary preconditions
   *
   */
  HASH_MAP(s, s_pre, {
    transformer post =
      statement_to_postcondition((transformer) s_pre, (statement) s);
    free_transformer(post);
  }, statement_temporary_precondition_map);
 
}

References add_cycle_dependency(), ancestor_cycle_head_to_scc(), CAR, CONS, CONTROL, control_map_get_blocs(), control_statement, control_test_p(), control_to_ancestor(), control_undefined, count, cycle_head_p(), cycle_head_to_scc(), cycle_to_flow_sensitive_preconditions(), ENDP, false_successors_only_p(), free_transformer(), gen_append(), gen_free_list(), gen_remove(), get_bool_property(), get_control_precondition(), get_cycle_dependencies(), HASH_MAP, hash_table_entry_count(), ifdebug, list_undefined, load_control_fix_point(), load_cycle_temporary_precondition(), MAKE_CONTROL_MAPPING, MAKE_STATEMENT_MAPPING, meaningless_control_p(), NIL, pips_assert, pips_debug, POP, precondition_add_condition_information(), print_control_node_unss_sem(), print_control_postcondition_map(), print_statement_temporary_precondition(), proper_cycle_head_to_scc(), remove_cycle_dependencies(), statement_identification(), statement_test(), statement_to_postcondition(), test_condition, transformer_apply(), transformer_convex_hull(), transformer_dup(), transformer_undefined, true_successors_only_p(), unstructured_control, unstructured_undefined, update_cycle_temporary_precondition(), and update_statement_temporary_precondition().

Referenced by unstructured_to_flow_sensitive_postconditions_or_transformers().

Here is the call graph for this function:

Here is the caller graph for this function:

free_control_fix_point_map()

static control_mapping free_control_fix_point_map ( control_mapping  control_fix_point_map )

static

all fix_points must be freed

return control_mapping_undefined;

Definition at line 412 of file unstructured.c.

{
  /* all fix_points must be freed */
  HASH_MAP(k,v,{
    free_transformer((transformer) v);
  }, control_fix_point_map);
 
  FREE_CONTROL_MAPPING(control_fix_point_map);
 
  /* return control_mapping_undefined; */
  return NULL;
}

References FREE_CONTROL_MAPPING, free_transformer(), and HASH_MAP.

Referenced by unstructured_to_flow_sensitive_postconditions_or_transformers().

Here is the call graph for this function:

Here is the caller graph for this function:

free_control_postcondition_map()

static control_mapping free_control_postcondition_map ( control_mapping  control_postcondition_map )

static

all postconditions must be freed

return control_mapping_undefined;

Definition at line 318 of file unstructured.c.

{
  /* all postconditions must be freed */
  HASH_MAP(k,v,{
    free_transformer((transformer) v);
  }, control_postcondition_map);
 
  FREE_CONTROL_MAPPING(control_postcondition_map);
 
  /* return control_mapping_undefined; */
  return NULL;
}

References FREE_CONTROL_MAPPING, free_transformer(), and HASH_MAP.

Referenced by unstructured_to_flow_sensitive_postconditions_or_transformers().

Here is the call graph for this function:

Here is the caller graph for this function:

get_control_precondition()

static transformer get_control_precondition ( control  c, control_mapping  control_postcondition_map, unstructured  u, transformer  pre_entry  )

static

Compute its precondition from the postconditions of its predecessor and from the entry precondition. Use arc pred->c information to deal with tests.

Do not forget the unstructured precondition for the entry node

FI: I do not know why it has to be replicated. Probably because the statement containing the unstructured and the statement of the entry node may share the same precondition.

This is not the entry node: without predecessors, it is unreachable

memory leak with lpre. pre_entry and postconditions cannot be freed: lpre cannot be freed during the first iteration

Definition at line 185 of file unstructured.c.

{
  transformer pre = transformer_undefined;
  list preds = control_predecessors(c);
 
  pips_assert("c is meaningfull", !meaningless_control_p(c));
 
  pips_debug(2, "Begin for node %p and statement %s\n", c,
             statement_identification(control_statement(c)));
 
  /* Compute its precondition from the postconditions of its predecessor
     and from the entry precondition. Use arc pred->c information to deal
     with tests. */
 
  if(c==unstructured_control(u)) {
    /* Do not forget the unstructured precondition for the entry node */
    /* FI: I do not know why it has to be replicated. Probably because the
       statement containing the unstructured and the statement of the
       entry node may share the same precondition. */
    pre = copy_transformer(pre_entry);
  }
  else {
    if(ENDP(preds)) {
      /* This is not the entry node: without predecessors, it is unreachable */
      pre = transformer_empty();
    }
    else {
      pre = load_arc_precondition(CONTROL(CAR(preds)), c, control_postcondition_map);
      POP(preds);
    }
  }
 
  FOREACH(CONTROL, pred, preds) {
    transformer npre = load_arc_precondition(pred, c, control_postcondition_map);
    transformer lpre = pre;
 
    pips_assert("The predecessor's postcondition npre is defined",
                !transformer_undefined_p(npre));
 
    pre = transformer_convex_hull(npre, lpre);
    /* memory leak with lpre. pre_entry and postconditions cannot be
       freed: lpre cannot be freed during the first iteration */
    if(pred!=CONTROL(CAR(preds)))
      free_transformer(lpre);
    lpre = pre;
  }
 
 
  ifdebug(2) {
    pips_debug(2, "End for node %p and statement %s with precondition %p:\n", c,
               statement_identification(control_statement(c)), pre);
    print_transformer(pre);
  }
 
  return pre;
}

References CAR, CONTROL, control_predecessors, control_statement, copy_transformer(), ENDP, FOREACH, free_transformer(), ifdebug, load_arc_precondition(), meaningless_control_p(), pips_assert, pips_debug, POP, print_transformer, statement_identification(), transformer_convex_hull(), transformer_empty(), transformer_undefined, transformer_undefined_p, and unstructured_control.

Referenced by cycle_to_flow_sensitive_preconditions(), and dag_to_flow_sensitive_preconditions().

Here is the call graph for this function:

Here is the caller graph for this function:

get_cycle_dependencies()

static list get_cycle_dependencies ( control  d, control_mapping  cycle_dependencies_map  )

static

Some cycle may appear nowhere but in the DAG and have no entries in the table.

In that case, they have an empty dependency list.

Definition at line 963 of file unstructured.c.

{
  list dependencies = (list) hash_get((hash_table) cycle_dependencies_map,
                                      (void *) d);
 
  if(dependencies == (list) HASH_UNDEFINED_VALUE) {
    dependencies = NIL;
  }
 
  return dependencies;
}

References hash_get(), HASH_UNDEFINED_VALUE, and NIL.

Referenced by dag_to_flow_sensitive_preconditions().

Here is the call graph for this function:

Here is the caller graph for this function:

load_arc_precondition()

static transformer load_arc_precondition ( control  pred, control  c, control_mapping  control_postcondition_map  )

static

forward declaration

Returns the precondition of c associated to arc pred->c in a newly allocated transformer.

pred must be unreachable, left over by the controlizer...

It would be nice to be able to check that it is unreachable... and that we do not land here because of a bug...

This should never happen.

let's assume that Bourdoncle's restructuring does not clutter the successor list too much.

Assume that the same node is in the true and false successor lists.

Do not bother with the test condition... and FI loose the side effects.

If side effects can be detected, perform a convex hull of the true and false branches as nothing else is available.

add the test condition

One of the true successors

One of the false successors

Definition at line 468 of file unstructured.c.

{
  transformer post = load_control_postcondition(pred, control_postcondition_map);
  transformer pre = transformer_undefined;
  int i = gen_position(c, control_successors(pred));
  int noo = gen_occurences(c, control_successors(pred));
 
  if(transformer_undefined_p(post)) {
    /* pred must be unreachable, left over by the controlizer... */
    /* It would be nice to be able to check that it is unreachable... and
       that we do not land here because of a bug...*/
    /* This should never happen. */
    pips_debug(2, "Failed for predecessor node pred=%p and node c=%p with map %p:\n",
               pred, c, control_postcondition_map);
    pips_assert("postconditions of predecessors are assumed initialized"
                " (see process_ready_node().", false);
    pre = transformer_empty();
  }
  else {
    pre = transformer_dup(post);
 
    pips_assert("c is a successor of pred", i!=0);
    /* let's assume that Bourdoncle's restructuring does not clutter the
       successor list too much. */
    pips_assert("c does not appear more than twice in the successor list",
                noo<=2);
 
    if(control_test_p(pred)) {
      statement stmt = control_statement(pred);
 
      pips_assert("stmt is a test", statement_test_p(stmt));
 
      if(noo==2) {
        /* Assume that the same node is in the true and false successor lists. */
        /* Do not bother with the test condition... and FI loose the side effects. */
        /* If side effects can be detected, perform a convex hull of the
           true and false branches as nothing else is available. */
        ;
      }
      else {
        /* add the test condition */
        expression e = test_condition(statement_test(stmt));
 
        if(i%2==1) { /* One of the true successors */
          pre = precondition_add_condition_information(pre, e,
                                                       transformer_undefined, true);
 
        }
        else{ /* One of the false successors */
          pre = precondition_add_condition_information(pre, e,
                                                       transformer_undefined, false);
        }
      }
    }
  }
  ifdebug(2) {
    string msg = control_test_p(pred)? (i%2==1? "true" : "false"): "standard";
    pips_debug(2, "End for %s arc of position %d between predecessor node pred=%p"
               " and node c=%p with precondition %p:\n",
               msg, i, pred, c, pre);
    print_transformer(pre);
  }
 
  return pre;
}

References control_statement, control_successors, control_test_p(), gen_occurences(), gen_position(), ifdebug, load_control_postcondition(), pips_assert, pips_debug, precondition_add_condition_information(), print_transformer, statement_test(), statement_test_p(), test_condition, transformer_dup(), transformer_empty(), transformer_undefined, and transformer_undefined_p.

Referenced by dag_or_cycle_to_flow_sensitive_postconditions_or_transformers(), get_control_precondition(), and process_ready_node().

Here is the call graph for this function:

Here is the caller graph for this function:

load_control_fix_point()

static transformer load_control_fix_point ( control  c, control_mapping  control_fix_point_map, hash_table  ancestor_map, hash_table  scc_map  )

static

The fix point can be linked either to the entry node of the scc or to the ancestor node.

The ancestor node is used by default, when transformer are not computed in context. So the argument is either the ancestor node (transformer out of context), or the call node (transformers computed in context) or the entry node (preconditions computed with transformers in context).

It is assumed that cycle_head_p(c) holds, but it is not assumed that its fixpoint is available..

Definition at line 342 of file unstructured.c.

{
  control c_a = control_undefined;
  transformer fptf = transformer_undefined;
 
  if(!get_bool_property("SEMANTICS_COMPUTE_TRANSFORMERS_IN_CONTEXT")) {
    c_a = control_to_ancestor(c, ancestor_map);
  }
  else {
    unstructured scc_u = ancestor_cycle_head_to_scc(c, scc_map);
    if(unstructured_undefined_p(scc_u))
      c_a = c;
    else
      c_a = unstructured_control(scc_u);
  }
 
  ifdebug(1) pips_assert("The control node pointing to the fix point is defined",
                         !control_undefined_p(c_a));
 
  fptf = (transformer)
    hash_get((hash_table) control_fix_point_map,
             (char *) c_a);
 
  if(fptf == (transformer) HASH_UNDEFINED_VALUE)
    fptf = transformer_undefined;
 
  pips_debug(5, "control %p, ancestor %p, transformer %p\n", c, c_a, fptf);
 
  /* It is assumed that cycle_head_p(c) holds, but it is not assumed that
     its fixpoint is available.. */
  /*
  ifdebug(1) pips_assert("The required fix point is defined",
                         !transformer_undefined_p(fptf));
  */
  return fptf;
}

References ancestor_cycle_head_to_scc(), control_to_ancestor(), control_undefined, control_undefined_p, get_bool_property(), hash_get(), HASH_UNDEFINED_VALUE, ifdebug, pips_assert, pips_debug, transformer_undefined, unstructured_control, and unstructured_undefined_p.

Referenced by cycle_to_flow_sensitive_preconditions(), dag_to_flow_sensitive_preconditions(), and process_ready_node().

Here is the call graph for this function:

Here is the caller graph for this function:

load_control_postcondition()

static transformer load_control_postcondition ( control  c, control_mapping  control_postcondition_map  )

static

Definition at line 169 of file unstructured.c.

{
  transformer post = (transformer)
    hash_get((hash_table) control_postcondition_map,
             (void *) c);
 
  if(post == (transformer) HASH_UNDEFINED_VALUE)
    post = transformer_undefined;
 
  return post;
}

References hash_get(), HASH_UNDEFINED_VALUE, and transformer_undefined.

Referenced by load_arc_precondition(), node_to_path_transformer_or_postcondition(), print_cycle_head_to_fixpoint(), process_unreachable_node(), ready_to_be_processed_p(), and unstructured_to_flow_sensitive_postconditions_or_transformers().

Here is the call graph for this function:

Here is the caller graph for this function:

load_cycle_fix_point()

transformer load_cycle_fix_point	(	control	c,
		hash_table	fix_point_map
	)

Parameters

fix_point_map

ix_point_map

Definition at line 544 of file unstructured.c.

{
  transformer fptf = transformer_undefined;
 
  if((fptf = (transformer) hash_get(fix_point_map, (void *) c))
     == (transformer) (HASH_UNDEFINED_VALUE)) 
    pips_assert("c is not a cycle head", false);
 
  return fptf;
}

References hash_get(), HASH_UNDEFINED_VALUE, pips_assert, and transformer_undefined.

Here is the call graph for this function:

load_cycle_temporary_precondition()

transformer load_cycle_temporary_precondition	(	control	c,
		control_mapping	cycle_temporary_precondition_map,
		hash_table	ancestor_map,
		hash_table scc_map	__attribute__(__unused__)
	)

Definition at line 1037 of file unstructured.c.

{
  transformer t_pre = transformer_undefined;
  control c_a = control_undefined;
 
  if(!get_bool_property("SEMANTICS_COMPUTE_TRANSFORMERS_IN_CONTEXT")) {
    c_a = control_to_ancestor(c, ancestor_map);
  }
  else {
    /*
    unstructured scc_u = ancestor_cycle_head_to_scc(c, scc_map);
    c_a = unstructured_control(scc_u);
    */
    c_a = c;
  }
 
  t_pre = (transformer) hash_get(cycle_temporary_precondition_map, (void *) c_a);
 
  pips_assert("The cycle precondition is available",
              t_pre != (transformer) HASH_UNDEFINED_VALUE);
 
  ifdebug(6) {
    pips_debug(6, "Precondition %p for cycle %p:\n", t_pre, c_a);
    print_transformer(t_pre);
  }
 
  return t_pre;
}

References control_to_ancestor(), control_undefined, get_bool_property(), hash_get(), HASH_UNDEFINED_VALUE, ifdebug, pips_assert, pips_debug, print_transformer, and transformer_undefined.

Referenced by dag_to_flow_sensitive_preconditions().

Here is the call graph for this function:

Here is the caller graph for this function:

load_statement_temporary_precondition()

transformer load_statement_temporary_precondition	(	statement	s,
		statement_mapping	statement_temporary_precondition_map
	)

Parameters

statement_temporary_precondition_map

tatement_temporary_precondition_map

Definition at line 1069 of file unstructured.c.

{
  transformer t_pre = (transformer) hash_get(statement_temporary_precondition_map, (void *) s);
 
  pips_assert("The cycle precondition is available",
              t_pre != (transformer) HASH_UNDEFINED_VALUE);
 
    return t_pre;
}

References hash_get(), HASH_UNDEFINED_VALUE, and pips_assert.

Referenced by cycle_to_flow_sensitive_preconditions().

Here is the call graph for this function:

Here is the caller graph for this function:

local_process_unreachable_node()

static void local_process_unreachable_node ( control  c, recursive_context *  pcontext  )

static

Definition at line 1781 of file unstructured.c.

{
  process_unreachable_node(c, pcontext->smap, pcontext->pcond);
}

References recursive_context::pcond, process_unreachable_node(), and recursive_context::smap.

Referenced by unstructured_to_flow_sensitive_postconditions_or_transformers().

Here is the call graph for this function:

Here is the caller graph for this function:

make_control_fix_point_map()

static control_mapping make_control_fix_point_map ( )

static

Definition at line 405 of file unstructured.c.

{
  control_mapping control_fix_point_map = NULL;
  control_fix_point_map = MAKE_CONTROL_MAPPING();
  return control_fix_point_map;
}

References MAKE_CONTROL_MAPPING.

Referenced by unstructured_to_flow_sensitive_postconditions_or_transformers().

Here is the caller graph for this function:

make_control_postcondition_map()

static control_mapping make_control_postcondition_map ( )

static

Definition at line 311 of file unstructured.c.

{
  control_mapping control_postcondition_map = NULL;
  control_postcondition_map = MAKE_CONTROL_MAPPING();
  return control_postcondition_map;
}

References MAKE_CONTROL_MAPPING.

Referenced by unstructured_to_flow_sensitive_postconditions_or_transformers().

Here is the caller graph for this function:

node_to_path_transformer_or_postcondition()

static void node_to_path_transformer_or_postcondition ( control  c, recursive_context *  pcontext  )

static

A debug function to prettyprint the result.

Definition at line 1787 of file unstructured.c.

{
  if(!meaningless_control_p(c)) {
    control_mapping control_postcondition_map = pcontext->smap;
    statement s = control_statement(c);
    transformer tf = load_control_postcondition(c, control_postcondition_map);
 
    pips_assert("Postcondition tf is defined", !transformer_undefined_p(tf));
    fprintf(stderr, "Statement %s", statement_identification(s));
    pips_assert("Transformer or postcondition is consistent",
                transformer_consistency_p(tf));
    print_transformer(tf);
  }
}

References control_statement, fprintf(), load_control_postcondition(), meaningless_control_p(), pips_assert, print_transformer, recursive_context::smap, statement_identification(), transformer_consistency_p(), and transformer_undefined_p.

Referenced by unstructured_to_flow_sensitive_postconditions_or_transformers().

Here is the call graph for this function:

Here is the caller graph for this function:

non_deterministic_unstructured_to_effects()

static list non_deterministic_unstructured_to_effects ( unstructured  scc, hash_table  ancestor_map, hash_table  scc_map  )

static

entry point

Definition at line 603 of file unstructured.c.

{
  list el = unstructured_to_effects(scc, ancestor_map, scc_map);
 
  ifdebug(6) {
    control e = unstructured_control(scc); /* entry point */
    pips_debug(6, "Effect list for unstructured %p with entry %p:\n",
               scc, e);
    print_effects(el);
  }
 
  return el;
}

References ifdebug, pips_debug, print_effects, unstructured_control, and unstructured_to_effects().

Referenced by process_ready_node().

Here is the call graph for this function:

Here is the caller graph for this function:

print_control_node_uns()

static void print_control_node_uns ( control  c )

static

semantical analysis

Computation of transformers and postconditions and total preconditions in unstructured (i.e. CFG).

Accurate results are obtained by restructuring CFG into a set of non-deterministic CFG's using Bourdoncle's partitioning as implemented in control/bourdoncle.c. The cycle heads are chosen using Bourdoncle's heuristics. Then the graph is augmented with new nodes in order that cycle heads are the only entry and exit node of the cycles in each scc. So the input CFG is transformed into a non-deterministic DAG. Some nodes of the DAG point to SCC's. Each SCC is represented by a DAG whose leaves point back to the cycle head. The SCC DAG may contain nodes pointing to sub-SCC's.

It is not clear if you want to store the node pre or postcondition. The postcondition may depend on the outgoing arc. But the precondition would have to be processed by the node transformer once for each arc. To avoid both problems the postconditions are stored without the control information. It is added later according to the outgoing arc considered. But it is not satisfactory to apply a reverse transformer to retrieve the precondition or to re-apply a convex hull on the input after having taken care of the potential cycle. All in all, it would be easier to store preconditions...

Transformers between the entry point and after the current node are very similar to postcondition between the module entry point and the current node. Transformers are obtained like precondition but without a precondition at the CFG entry point.

It is possible to store the star or the plus fix points. I first stored the star fix points. It is often needed. It is safe because it can be applied several times without impacting the result. However, it does not retain information about the cycle body transformer. Because the convex hull operator looses information, it is more accurate to use the plus fix point and to apply a convex hull to the direct precondition and to the cycle output. Thus, if the entry node is a test, its conditions can be added before the convex hull is performed.

It might be useful to add a pseudo-node as predecessor of the CFG entry node. This pseudo-node would simplify the algorithms and the function profiles. Its post-condition would be the precondition of the CFG or no information. Without it, each node must be checked to see if it is the entry node because, then, it has an extra-predecessor.

Francois Irigoin, July 2002 (First version: October 2000)

Note: Bourdoncle's heuristics minimizes the number of cycles under the assumption that most information is lost when performing a widening. We do not use widening but direct computation of an upper approximation of the transition closure. And sometimes, a lot of information is lost when performing convex hulls of transformers. So, using transformers, it would be better to maximize the number of cycles to minimize the number of paths in each cycle. include <stdlib.h>

Definition at line 122 of file unstructured.c.

{
  fprintf(stderr,
          "ctr %p, %zd preds, %zd succs: %s",
          c,
          gen_length(control_predecessors(c)),
          gen_length(control_successors(c)),
          safe_statement_identification(control_statement(c)));
  fprintf(stderr,"\tsuccessors:\n");
  MAP(CONTROL, s, {
    fprintf(stderr, "\t\t%p %s", s,
            safe_statement_identification(control_statement(s)));
  }, control_successors(c));
  fprintf(stderr,"\tpredecessors:\n");
  MAP(CONTROL, p, {
    fprintf(stderr, "\t\t%p %s", p,
            safe_statement_identification(control_statement(p)));
  }, control_predecessors(c));
  fprintf(stderr, "\n");
}

References CONTROL, control_predecessors, control_statement, control_successors, fprintf(), gen_length(), MAP, and safe_statement_identification().

Referenced by unstructured_to_flow_sensitive_postconditions_or_transformers().

Here is the call graph for this function:

Here is the caller graph for this function:

print_control_node_unss_sem()

static void print_control_node_unss_sem ( list  l )

static

Definition at line 143 of file unstructured.c.

{
  if(ENDP(l)) {
    fprintf(stderr, "empty control list");
  }
  else {
    MAP(CONTROL, c, {
      fprintf(stderr, "%p, %s", c,
              safe_statement_identification(control_statement(c)));
    }, l);
  }
  fprintf(stderr, "\n");
}

References CONTROL, control_statement, ENDP, fprintf(), MAP, and safe_statement_identification().

Referenced by cycle_to_flow_sensitive_preconditions(), dag_or_cycle_to_flow_sensitive_postconditions_or_transformers(), and dag_to_flow_sensitive_preconditions().

Here is the call graph for this function:

Here is the caller graph for this function:

print_control_postcondition_map()

void print_control_postcondition_map

(

control_mapping

control_postcondition_map

)

unstructured.c

Parameters

control_postcondition_map

ontrol_postcondition_map

Definition at line 294 of file unstructured.c.

{
  if(hash_table_entry_count(control_postcondition_map)>0) {
    HASH_MAP(c, p, {
      statement s = control_statement((control) c);
      fprintf(stderr, "Control %p, Statement %s, Temporary postcondition:\n",
              c, statement_identification(s));
      print_transformer((transformer) p);
    }, control_postcondition_map);
  }
  else {
    pips_assert("The CFG contains at least one node with one statement",
                false);
  }
}

References control_statement, fprintf(), HASH_MAP, hash_table_entry_count(), pips_assert, print_transformer, and statement_identification().

Referenced by dag_to_flow_sensitive_preconditions().

Here is the call graph for this function:

Here is the caller graph for this function:

print_cycle_head_to_fixpoint()

static void print_cycle_head_to_fixpoint ( control  c, recursive_context *  pcontext  )

static

A debug function to prettyprint the fix points.

Most control nodes are not associated to a fix point

Definition at line 1803 of file unstructured.c.

{
  control_mapping control_fix_point_map = pcontext->smap;
  statement s = control_statement(c);
  transformer tf = load_control_postcondition(c, control_fix_point_map);
 
  /* Most control nodes are not associated to a fix point */
  if(!transformer_undefined_p(tf)) {
    fprintf(stderr, "Statement %s", statement_identification(s));
    pips_assert("Transformer or postcondition is consistent",
                transformer_consistency_p(tf));
    print_transformer(tf);
  }
}

References control_statement, fprintf(), load_control_postcondition(), pips_assert, print_transformer, recursive_context::smap, statement_identification(), transformer_consistency_p(), and transformer_undefined_p.

Referenced by unstructured_to_flow_sensitive_postconditions_or_transformers().

Here is the call graph for this function:

Here is the caller graph for this function:

print_statement_temporary_precondition()

void print_statement_temporary_precondition

(

statement_mapping

statement_temporary_precondition_map

)

Parameters

statement_temporary_precondition_map

tatement_temporary_precondition_map

Definition at line 1006 of file unstructured.c.

{
  if(hash_table_entry_count(statement_temporary_precondition_map)>0) {
    HASH_MAP(s, p, {
      fprintf(stderr, "Statement %s, Temporary precondition:\n",
              statement_identification((statement) s));
      print_transformer((transformer) p);
    }, statement_temporary_precondition_map);
  }
  else {
    pips_assert("The DAG contains at least one control node with one statement", false);
  }
}

References fprintf(), HASH_MAP, hash_table_entry_count(), pips_assert, print_transformer, and statement_identification().

Referenced by dag_to_flow_sensitive_preconditions().

Here is the call graph for this function:

Here is the caller graph for this function:

process_ready_node()

static void process_ready_node ( control  c, transformer  pre_entry, transformer  n_pre, unstructured  u, control_mapping  control_postcondition_map, hash_table  ancestor_map, hash_table  scc_map, list  partition, control_mapping  fix_point_map, bool  postcondition_p  )

static

Compute its precondition pre from the postconditions of its predecessor and from the entry precondition. Use arc pred->c information to deal with tests.

Do not forget the unstructured precondition for the entry node

FI: I do not know why it has to be replicated. Probably because the statement containing the unstructured and the statement of the entry node may share the same precondition.

memory leak with lpre. pre_entry and postconditions cannot be freed: lpre cannot be freed during the first iteration

if(pred!=CONTROL(CAR(preds))) free_transformer(lpre);

Add the information from the current precondition.

If the control is a cycle head, find and apply its fix point tranformer to the precondition before proceeding into the node itself

unstructured_to_flow_insensitive_transformer(scc_u) cannot be used because it assumes that all transformers for statements in scc_u are defined, which is not true yet.

transformer tf_u = unstructured_to_flow_insensitive_transformer(scc_u);

n_pre_u is assumed more accurate than n_pre

Bourdoncle's processing ordering

A non-deterministic acyclic control flow graph

Mapping from non-deterministic nodes to deterministic nodes

mapping from deterministic nodes to non-deterministic cycles

precondition on entry

precondition true for any node of scc_u.

Compute transformers

The cycle is entered

Or the cycle is not entered and the store is not in fptf's domain.

Have we followed a true or a false branch? We'll know later but it is better to add this information before the convex hull is performed.

FI: I do not know why an empty context is passed down.

Propagate the precondition thru the node to obtain a postcondition which does not include arc information (FI: hard if side-effects?)

FI: The transformer might have to be recomputed before the call if the option is selected? It does not seem to be located in statement_to_postcondition()

FI: is this correct when the statement is a test since the node only exploits the condition? It might be because of the convex hull nullifying the condition and hence the arc information.

FI: statement_to_postcondition() cannot always be used because the statement may appear in different non-deterministic nodes; pre is only of of the many preconditions that can hold before stmt is executed; statement_to_postcondition() should be called later when the whole unstructured has been analyzed.

post = statement_to_postcondition(pre, stmt);

The statement transformer may have been computed earlier thru a fix point calculation, but the transformer may not be correct if it were computed in context (property SEMANTICS_COMPUTE_TRANSFORMERS_IN_CONTEXT true).

We are in trouble: the transformer attached to a statement should be the convex hull of its transformers computed in all its context. Our options:

1. fix statement_to_transformer() to perform the convex hulls when needed
2. turn off the property SEMANTICS_COMPUTE_TRANSFORMERS_IN_CONTEXT as soon as an untructured is entered and restore it on exit
3. assume that statement stmt is not a compound statement and try to fix the problem locally.

Let's live very dangerously and try 1...

Definition at line 630 of file unstructured.c.

{
  transformer post = transformer_undefined;
  statement stmt = control_statement(c);
  list preds = control_predecessors(c);
  transformer pre = transformer_undefined;
 
  ifdebug(2) {
    pips_debug(2, "Begin for control %p with pre_entry=%p:\n", c, pre_entry);
    print_transformer(pre_entry);
    pips_debug(2, "Begin with n_pre=%p:\n", n_pre);
    print_transformer(n_pre);
    pips_debug(5, "to process node %s\n", statement_identification(control_statement(c)));
  }
 
  /* Compute its precondition pre from the postconditions of its predecessor
     and from the entry precondition. Use arc pred->c information to deal
     with tests. */
 
  if(c==unstructured_control(u)) {
    /* Do not forget the unstructured precondition for the entry node */
    /* FI: I do not know why it has to be replicated. Probably because the
       statement containing the unstructured and the statement of the
       entry node may share the same precondition. */
    pre = copy_transformer(pre_entry);
  }
  else {
    pre = load_arc_precondition(CONTROL(CAR(preds)), c, control_postcondition_map);
    POP(preds);
  }
 
  MAP(CONTROL, pred, {
    transformer npre = load_arc_precondition(pred, c, control_postcondition_map);
    transformer lpre = pre;
 
    pre = transformer_convex_hull(npre, lpre);
    /* memory leak with lpre. pre_entry and postconditions cannot be
       freed: lpre cannot be freed during the first iteration */
    /* if(pred!=CONTROL(CAR(preds))) free_transformer(lpre); */
    free_transformer(lpre);
    free_transformer(npre);
    lpre = pre;
  }, preds);
 
  ifdebug(2) {
    pips_debug(2, "Precondition %p for control %p:\n", pre, c);
    print_transformer(pre);
  }
 
  if(refine_transformers_p && !meaningless_control_p(c)) {
    /* Add the information from the current precondition. */
    statement cs = control_statement(c);
    transformer prev_pre = load_statement_precondition(cs);
    transformer r_prev_pre = transformer_range(prev_pre);
 
    pre = transformer_range_intersection(pre, r_prev_pre);
    free_transformer(r_prev_pre);
    ifdebug(2) {
      pips_debug(2, "Refined precondition %p for control %p:\n", pre, c);
      print_transformer(pre);
    }
  }
 
  /* If the control is a cycle head, find and apply its fix point
     tranformer to the precondition before proceeding into the node itself */
 
  if(cycle_head_p(c, ancestor_map, scc_map)) {
    transformer fptf = load_control_fix_point(c, fix_point_map, ancestor_map, scc_map);
    transformer pre_cycle = transformer_undefined;
    transformer pre_no_cycle = transformer_undefined;
 
    if(transformer_undefined_p(fptf)) {
      unstructured scc_u = cycle_head_to_scc(c, ancestor_map, scc_map);
      /* unstructured_to_flow_insensitive_transformer(scc_u) cannot be
         used because it assumes that all transformers for statements in
         scc_u are defined, which is not true yet. */
      /* transformer tf_u = unstructured_to_flow_insensitive_transformer(scc_u); */
      list scc_e = non_deterministic_unstructured_to_effects(scc_u, ancestor_map, scc_map);
      transformer tf_u = effects_to_transformer(scc_e);
      /* n_pre_u is assumed more accurate than n_pre */
      transformer n_pre_u = invariant_wrt_transformer(pre, tf_u);
 
      ifdebug(6) {
        pips_debug(6, "Rough fixpoint transformer %p for unstructured %p:\n", tf_u, scc_u);
        print_transformer(tf_u);
        pips_debug(6, "Resulting in generic node precondition %p:\n", n_pre_u);
        print_transformer(n_pre_u);
      }
 
      free_transformer(tf_u);
      gen_free_list(scc_e);
 
      fptf = cycle_to_flow_sensitive_postconditions_or_transformers
        (partition, /* Bourdoncle's processing ordering */
         scc_u, /* A non-deterministic acyclic control flow graph */
         ancestor_map, /* Mapping from non-deterministic nodes to deterministic nodes */
         scc_map, /* mapping from deterministic nodes to non-deterministic cycles */
         fix_point_map,
         pre, /* precondition on entry */
         n_pre_u, /* precondition true for any node of scc_u. */
         control_postcondition_map, /* */
         false); /* Compute transformers */
 
      ifdebug(2) {
        pips_debug(2, "Fixpoint transformer %p for control %p:\n", fptf, c);
        print_transformer(fptf);
      }
    }
 
    /* The cycle is entered */
    pre_cycle = transformer_apply(fptf, pre);
    /* Or the cycle is not entered and the store is not in fptf's domain. */
    pre_no_cycle = transformer_dup(pre);
 
    if(control_test_p(c)) {
      /* Have we followed a true or a false branch? We'll know later but
         it is better to add this information before the convex hull is
         performed. */
      statement stmt = control_statement(c);
      expression e = test_condition(statement_test(stmt));
 
      /* FI: I do not know why an empty context is passed down. */
      if(true_successors_only_p(c)) {
        pre_no_cycle = precondition_add_condition_information(pre_no_cycle, e,
                                                              transformer_undefined, true);
      }
      else if(false_successors_only_p(c)) {
        pre_no_cycle = precondition_add_condition_information(pre_no_cycle, e,
                                                              transformer_undefined, false);
      }
    }
    free_transformer(pre);
    pre = transformer_convex_hull(pre_cycle, pre_no_cycle);
 
    ifdebug(2) {
      pips_debug(2, "Precondition after cycle execution %p for control %p:\n", pre, c);
      print_transformer(pre);
      pips_debug(2, "derived from pre_cycle %p:\n", pre_cycle);
      print_transformer(pre_cycle);
      pips_debug(2, "and from pre_no_cycle %p:\n", pre_no_cycle);
      print_transformer(pre_no_cycle);
    }
 
    free_transformer(pre_cycle);
    free_transformer(pre_no_cycle);
  }
 
  /* Propagate the precondition thru the node to obtain a postcondition
     which does not include arc information (FI: hard if side-effects?) */
 
  if(postcondition_p) {
    /* FI: The transformer might have to be recomputed before the call if
       the option is selected? It does not seem to be located in
       statement_to_postcondition() */
    /* FI: is this correct when the statement is a test since the node
       only exploits the condition? It might be because of the convex hull
       nullifying the condition and hence the arc information. */
    /* FI: statement_to_postcondition() cannot always be used because the
       statement may appear in different non-deterministic nodes; pre is
       only of of the many preconditions that can hold before stmt is
       executed; statement_to_postcondition() should be called later when
       the whole unstructured has been analyzed. */
    /* post = statement_to_postcondition(pre, stmt); */
    transformer tf = load_statement_transformer(stmt);
 
    pips_assert("The statement transformer is defined",
                !transformer_undefined_p(tf));
    post = transformer_apply(tf, pre);
 
    ifdebug(2) {
      pips_debug(2, "Postcondition %p for control %p:\n", post, c);
      print_transformer(post);
      pips_debug(2, "derived from pre %p:\n", pre);
      print_transformer(pre);
      pips_debug(2, "and from tf %p:\n", tf);
      print_transformer(tf);
    }
  }
  else {
    /* The statement transformer may have been computed earlier thru a fix
       point calculation, but the transformer may not be correct if it
       were computed in context (property SEMANTICS_COMPUTE_TRANSFORMERS_IN_CONTEXT true). */
    transformer tfp = load_statement_transformer(stmt);
    transformer tf = transformer_undefined;
 
    if(transformer_undefined_p(tfp)) {
      tf = statement_to_transformer(stmt, pre);
    }
    else {
      if(get_bool_property("SEMANTICS_COMPUTE_TRANSFORMERS_IN_CONTEXT")) {
        /* We are in trouble: the transformer attached to a statement
           should be the convex hull of its transformers computed in all
           its context. Our options:
 
           1. fix statement_to_transformer() to perform the convex hulls when needed
 
           2. turn off the property
           SEMANTICS_COMPUTE_TRANSFORMERS_IN_CONTEXT as soon as an
           untructured is entered and restore it on exit
 
           3. assume that statement stmt is not a compound statement and
           try to fix the problem locally.
 
           Let's live very dangerously and try 1... */
        transformer tfn = statement_to_transformer(stmt, pre);
 
        tf = tfn;
      }
      else {
        tf = tfp;
      }
    }
    post = transformer_apply(tf, pre);
  }
 
  store_control_postcondition(c, post, control_postcondition_map);
 
  ifdebug(2) {
    pips_debug(2, "Postcondition %p stored for control %p:\n", post, c);
    print_transformer(post);
  }
}

References CAR, CONTROL, control_predecessors, control_statement, control_test_p(), copy_transformer(), cycle_head_p(), cycle_head_to_scc(), cycle_to_flow_sensitive_postconditions_or_transformers(), effects_to_transformer(), false_successors_only_p(), free_transformer(), gen_free_list(), get_bool_property(), ifdebug, invariant_wrt_transformer(), load_arc_precondition(), load_control_fix_point(), load_statement_precondition(), load_statement_transformer(), MAP, meaningless_control_p(), non_deterministic_unstructured_to_effects(), pips_assert, pips_debug, POP, precondition_add_condition_information(), print_transformer, refine_transformers_p, statement_identification(), statement_test(), statement_to_transformer(), store_control_postcondition(), test_condition, transformer_apply(), transformer_convex_hull(), transformer_dup(), transformer_range(), transformer_range_intersection(), transformer_undefined, transformer_undefined_p, true_successors_only_p(), and unstructured_control.

Referenced by dag_or_cycle_to_flow_sensitive_postconditions_or_transformers().

Here is the call graph for this function:

Here is the caller graph for this function:

process_unreachable_node()

static bool process_unreachable_node ( control  c, control_mapping  control_postcondition_map, bool  postcondition_p  )

static

Careful, this may have been done earlier by the CONTROL_MAP in unstructured_to_transformers()

FI: We should use the generic node precondition n_pre; it should be an additional component in the context.

Problem with ELSIP in ARC2D after partial redundancy elimination

pips_internal_error(statement_identification(s));

Problem with SHALLOW in SWIM

Definition at line 862 of file unstructured.c.

{
  statement s = control_statement(c);
 
  pips_debug(9,"Statement %s", safe_statement_identification(s));
 
  if(!meaningless_control_p(c)) {
    if(statement_ordering(s)==STATEMENT_ORDERING_UNDEFINED) {
      pips_internal_error("Improper control restructuration, statement with no ordering:%s",
                          statement_identification(s));
    }
 
    if(transformer_undefined_p
       (load_control_postcondition(c, control_postcondition_map))) {
      transformer post = transformer_undefined;
 
      if(postcondition_p) {
        transformer pre = transformer_empty();
        post = statement_to_postcondition(pre, s);
      }
      else {
        /* Careful, this may have been done earlier by the CONTROL_MAP in
           unstructured_to_transformers() */
        if(transformer_undefined_p(load_statement_transformer(s))) {
          /* FI: We should use the generic node precondition n_pre; it
             should be an additional component in the context. */
          (void) statement_to_transformer(s, transformer_undefined);
        }
        post = transformer_empty();
      }
 
      semantics_user_warning("After restructuration, unexpected unreachable node:%s",
                        statement_identification(s));
 
      store_control_postcondition(c, post, control_postcondition_map);
    }
    else if(postcondition_p
            && transformer_undefined_p(load_statement_precondition(s))) {
      /* Problem with ELSIP in ARC2D after partial redundancy elimination */
      /* pips_internal_error(statement_identification(s)); */
      transformer pre = transformer_empty();
      transformer post = statement_to_postcondition(pre, s);
 
      pips_assert("the new postcondition is empty", transformer_empty_p(post));
      pips_assert("the previous postcondition is empty",
                  transformer_empty_p(load_control_postcondition(c, control_postcondition_map)));
 
      semantics_user_warning("After restructuration (?),"
                        " postcondtion for unexpected unreachable node:%s",
                        statement_identification(s));
    }
    else if(!postcondition_p
            && transformer_undefined_p(load_statement_transformer(s))) {
      /* Problem with SHALLOW in SWIM */
      (void) statement_to_transformer(s, transformer_undefined);
 
      semantics_user_warning("After restructuration (?),"
                        " transformer for unexpected unreachable node:%s",
                        statement_identification(s));
    }
  }
  return true;
}

References control_statement, load_control_postcondition(), load_statement_precondition(), load_statement_transformer(), meaningless_control_p(), pips_assert, pips_debug, pips_internal_error, safe_statement_identification(), semantics_user_warning, statement_identification(), statement_ordering, STATEMENT_ORDERING_UNDEFINED, statement_to_postcondition(), statement_to_transformer(), store_control_postcondition(), transformer_empty(), transformer_empty_p(), transformer_undefined, and transformer_undefined_p.

Referenced by local_process_unreachable_node().

Here is the call graph for this function:

Here is the caller graph for this function:

ready_to_be_processed_p()

static bool ready_to_be_processed_p ( control  c, list  to_be_processed, list  still_to_be_processed, list  already_processed, control_mapping  control_postcondition_map  )

static

a control is ready to be processed if all its predecessors have known postconditions or can receive a trivial empty postcondition

useless, except for debugging

postcondition must be empty because pred is not reachable

transformer pre = transformer_empty();

transformer post = statement_to_postcondition(pre, stmt);

Definition at line 427 of file unstructured.c.

{
  bool ready = true;
  MAP(CONTROL, pred, {
    if(gen_in_list_p(pred, already_processed)) {
      /* useless, except for debugging */
      ready &= true;
    }
    else if(!gen_in_list_p(pred, to_be_processed)) {
      /* postcondition must be empty because pred is not reachable */
      /* transformer pre = transformer_empty(); */
      transformer post = load_control_postcondition(pred, control_postcondition_map);
 
      if(transformer_undefined_p(post)) {
        post = transformer_empty();
        /* transformer post = statement_to_postcondition(pre, stmt); */
        store_control_postcondition(pred, post, control_postcondition_map);
      }
      else {
        pips_assert("Postcondition for unreachable nodes must be empty",
                    transformer_empty_p(post));
      }
    }
    else if(gen_in_list_p(pred, still_to_be_processed)) {
      ready &= false;
    }
    else {
      pips_internal_error("node pred does not belong to any category: %s",
                 statement_identification(control_statement(pred)));
    }
  }, control_predecessors(c));
  return ready;
}

References CONTROL, control_predecessors, control_statement, gen_in_list_p(), load_control_postcondition(), MAP, pips_assert, pips_internal_error, statement_identification(), store_control_postcondition(), transformer_empty(), transformer_empty_p(), and transformer_undefined_p.

Referenced by cycle_to_flow_sensitive_preconditions(), and dag_or_cycle_to_flow_sensitive_postconditions_or_transformers().

Here is the call graph for this function:

Here is the caller graph for this function:

remove_cycle_dependencies()

static void remove_cycle_dependencies ( control  c, control_mapping  cycle_dependencies_map  )

static

c has been processed and no other cycle can depend on it

Oops... gen_remove() might change the pointer

Definition at line 951 of file unstructured.c.

{
  HASH_MAP(d, dependencies, {
    /* Oops... gen_remove() might change the pointer */
    gen_remove((list*) (&dependencies), c);
    hash_update((hash_table) (cycle_dependencies_map),
           (void *) d, (void *) dependencies);
  }, cycle_dependencies_map);
}

References gen_remove(), HASH_MAP, and hash_update().

Referenced by dag_to_flow_sensitive_preconditions().

Here is the call graph for this function:

Here is the caller graph for this function:

store_control_fix_point()

static void store_control_fix_point ( control  c, transformer  fptf, control_mapping  control_fix_point_map  )

static

Definition at line 382 of file unstructured.c.

{
  statement stat = control_statement(c);
 
  pips_assert("The statement is defined",
              !meaningless_control_p(c) && !statement_undefined_p(stat));
  pips_debug(8, "Store fix_point for control %p: %s\n",
             c, statement_identification(stat));
  ifdebug(8) {
    print_transformer(fptf);
  }
 
  pips_assert("The fix_point to insert is consistent",
              transformer_consistency_p(fptf));
 
  pips_assert("The fix_point is not defined yet",
              hash_get((hash_table) control_fix_point_map, (void *) c)
              == HASH_UNDEFINED_VALUE);
  hash_put((hash_table) (control_fix_point_map),
           (void *)c, (void *) fptf);
}

References control_statement, hash_get(), hash_put(), HASH_UNDEFINED_VALUE, ifdebug, meaningless_control_p(), pips_assert, pips_debug, print_transformer, statement_identification(), statement_undefined_p, and transformer_consistency_p().

Referenced by dag_or_cycle_to_flow_sensitive_postconditions_or_transformers().

Here is the call graph for this function:

Here is the caller graph for this function:

store_control_postcondition()

static void store_control_postcondition ( control  c, transformer  post, control_mapping  control_postcondition_map  )

static

Definition at line 245 of file unstructured.c.

{
  statement stat = control_statement(c);
 
  pips_assert("The statement is defined",
              !meaningless_control_p(c) && !statement_undefined_p(stat));
  pips_debug(6, "Store postcondition for control %p: %s\n",
             c, statement_identification(stat));
  ifdebug(6) {
    print_transformer(post);
  }
 
  pips_assert("The postcondition to insert is consistent", 
              transformer_consistency_p(post));
 
  pips_assert("The postcondition is not defined yet", 
              hash_get((hash_table) control_postcondition_map, (void *) c)
              == HASH_UNDEFINED_VALUE);
  hash_put((hash_table) (control_postcondition_map),
           (void *) c, (void *) post);
}

References control_statement, hash_get(), hash_put(), HASH_UNDEFINED_VALUE, ifdebug, meaningless_control_p(), pips_assert, pips_debug, print_transformer, statement_identification(), statement_undefined_p, and transformer_consistency_p().

Referenced by dag_or_cycle_to_flow_sensitive_postconditions_or_transformers(), process_ready_node(), process_unreachable_node(), and ready_to_be_processed_p().

Here is the call graph for this function:

Here is the caller graph for this function:

unreachable_node_to_transformer()

static void unreachable_node_to_transformer ( control  c )

static

Definition at line 2158 of file unstructured.c.

{
  statement s = control_statement(c);
 
  pips_debug(9,"Statement %s", statement_identification(s));
 
  if(statement_ordering(s)==STATEMENT_ORDERING_UNDEFINED) {
    semantics_user_warning("Improper control restructuration, statement with no ordering:%s"
                      "May result from an unreachable exit node\n",
                      statement_identification(s));
  }
 
  if(transformer_undefined_p(load_statement_transformer(s))) {
    semantics_user_warning("After restructuration, unexpected unreachable node:%s",
                      statement_identification(s));
    (void) statement_to_transformer(s, transformer_undefined);
  }
}

References control_statement, load_statement_transformer(), pips_debug, semantics_user_warning, statement_identification(), statement_ordering, STATEMENT_ORDERING_UNDEFINED, statement_to_transformer(), transformer_undefined, and transformer_undefined_p.

Referenced by unstructured_to_transformer().

Here is the call graph for this function:

Here is the caller graph for this function:

unstructured_to_effects()

static list unstructured_to_effects ( unstructured  scc, hash_table  ancestor_map, hash_table  scc_map  )

static

In fact, non-deterministic unstructured to effects.

entry point

Definition at line 556 of file unstructured.c.

{
  list el = NIL;
  list nodes = NIL;
  control e = unstructured_control(scc); /* entry point */
 
  pips_debug(6, "Effect list for unstructured %p with entry %p:begin\n",
             scc, e);
 
  FORWARD_CONTROL_MAP(c, {
    if(!meaningless_control_p(c)) {
      statement s = control_statement(c);
      list sel = load_cumulated_rw_effects_list(s);
 
      el = EffectsMayUnion(el, gen_full_copy_list(sel), effects_same_action_p);
 
      if(cycle_head_p(c, ancestor_map, scc_map)) {
        unstructured sub_scc = cycle_head_to_scc(c, ancestor_map, scc_map);
        if(scc!=sub_scc) {
          list sl = unstructured_to_effects(sub_scc, ancestor_map, scc_map);
          list nl = list_undefined;
          ifdebug(7) {
            pips_debug(7, "Sub-effect list for unstructured %p with entry %p:\n",
                     sub_scc, unstructured_control(sub_scc));
            print_effects(sl);
            pips_debug(7, "Union with previous effects:\n");
            print_effects(el);
          }
          nl = EffectsMayUnion(el, sl, effects_same_action_p);
          el = nl;
          ifdebug(7) {
            pips_debug(7, "Resulting in:\n");
            print_effects(el);
          }
        }
      }
    }
  }, e, nodes);
  gen_free_list(nodes);
 
  pips_debug(6, "Effect list for unstructured %p with entry %p:end\n",
             scc, e);
 
  return el;
}

References control_statement, cycle_head_p(), cycle_head_to_scc(), effects_same_action_p(), EffectsMayUnion(), FORWARD_CONTROL_MAP, gen_free_list(), gen_full_copy_list(), ifdebug, list_undefined, load_cumulated_rw_effects_list(), meaningless_control_p(), NIL, pips_debug, print_effects, and unstructured_control.

Referenced by non_deterministic_unstructured_to_effects().

Here is the call graph for this function:

Here is the caller graph for this function:

unstructured_to_flow_insensitive_transformer()

transformer unstructured_to_flow_insensitive_transformer

(

unstructured

u

)

This simple fix-point over-approximates the CFG by a fully connected graph.

Each vertex can be executed at any time any number of times.

The fix point is easy to compute because it is the fix point of the convex hull all each node transformers.

The result is sometimes surprising as users see the real paths and cannot understand why a variable is declared modified when it obviously is not. This mostly choses in node preconditions since the overall unstructured transformer is not displayed usually and since it is globally correct.

But it is a perfectly valid over-approximation usable by automatic analyses.

Using the effects of the unstructured to derive a fix point leads to the same surprise although it is as correct, using the same over approximation of the control flow graph but a cruder version of the transformers.

This function is also used when computing preconditions if the exit node is not reached (?). It assumes that transformers for all statements in the unstructured have already been computed.

Two modes are possible: the transitive closure of the convex hull of all elementary transformers, or the transitive closure of the transformer list.

Assume any reachable node is executed at each iteration. A fix-point of the result can be used to approximate the node preconditions. Some nodes can be discarded because they do not modify the store such as IF statements (always) and CONTINUE statements (if they do not link the entry and the exit nodes).

Entry node

transformer_convex_hull has side effects on its arguments:-(

Should be fixed now, 29 June 2000

transformer tf_st = copy_transformer(load_statement_transformer(st));

Any side effect?

test

continue

other

Definition at line 2206 of file unstructured.c.

{
  /* Assume any reachable node is executed at each iteration. A fix-point
     of the result can be used to approximate the node preconditions. Some
     nodes can be discarded because they do not modify the store such as
     IF statements (always) and CONTINUE statements (if they do not link
     the entry and the exit nodes). */
 
  list nodes = NIL;
  /* Entry node */
  control entry_node = unstructured_control(u);
  control exit_node = unstructured_exit(u);
  transformer tf_u = transformer_empty();
  transformer fp_tf_u = transformer_undefined;
  bool tfl_p = get_bool_property("SEMANTICS_USE_TRANSFORMER_LISTS");
  list tfl = NIL;
 
  pips_debug(8,"begin\n");
 
  FORWARD_CONTROL_MAP(c, {
    statement st = control_statement(c);
    /* transformer_convex_hull has side effects on its arguments:-( */
    /* Should be fixed now, 29 June 2000 */
    /* transformer tf_st = copy_transformer(load_statement_transformer(st)); */
    transformer tf_st = load_statement_transformer(st);
    transformer tf_old = tf_u;
 
    if(statement_test_p(st)) {
      /* Any side effect? */
      if(!ENDP(transformer_arguments(tf_st))) {
        if(tfl_p) {
          tfl = CONS(TRANSFORMER, tf_st, tfl);
        }
        else {
          tf_u = transformer_convex_hull(tf_old, tf_st); /* test */
          free_transformer(tf_old);
        }
      }
    }
    else {
      if(continue_statement_p(st)) {
        if(gen_find_eq(entry_node, control_predecessors(c))!=chunk_undefined
           && gen_find_eq(exit_node, control_successors(c))!=chunk_undefined) {
        if(tfl_p) {
          tfl = CONS(TRANSFORMER, tf_st, tfl);
        }
        else {
          tf_u = transformer_convex_hull(tf_old, tf_st); /* continue */
          free_transformer(tf_old);
        }
        }
      }
      else {
        if(tfl_p) {
          tfl = CONS(TRANSFORMER, tf_st, tfl);
        }
        else {
        tf_u = transformer_convex_hull(tf_old, tf_st); /* other */
        free_transformer(tf_old);
        }
      }
    }
 
    ifdebug(1) {
      pips_assert("tf_st is internally consistent",
                  transformer_internal_consistency_p(tf_st));
      if(!tfl_p)
        pips_assert("tf_u is internally consistent",
                    transformer_internal_consistency_p(tf_u));
    }
 
  }, entry_node, nodes) ;
 
  gen_free_list(nodes) ;
 
  if(tfl_p) {
    // FI: apparently, we need T* rather than T+
      fp_tf_u = transformer_list_transitive_closure(tfl);
      gen_free_list(tfl);
  }
  else
    fp_tf_u = (*transformer_fix_point_operator)(tf_u);
 
  ifdebug(8) {
    pips_debug(8,"Result for one step tf_u:\n");
    print_transformer(tf_u);
    pips_assert("tf_u is internally consistent",
                transformer_internal_consistency_p(tf_u));
    pips_debug(8,"Result for fix-point fp_tf_u:\n");
    print_transformer(fp_tf_u);
    pips_assert("fp_tf_u is internally consistent",
                transformer_internal_consistency_p(fp_tf_u));
  }
 
  pips_debug(8,"end\n");
 
  return fp_tf_u;
}

References chunk_undefined, CONS, continue_statement_p(), control_predecessors, control_statement, control_successors, ENDP, FORWARD_CONTROL_MAP, free_transformer(), gen_find_eq(), gen_free_list(), get_bool_property(), ifdebug, load_statement_transformer(), NIL, pips_assert, pips_debug, print_transformer, statement_test_p(), TRANSFORMER, transformer_arguments, transformer_convex_hull(), transformer_empty(), transformer_internal_consistency_p(), transformer_list_transitive_closure(), transformer_undefined, unstructured_control, and unstructured_exit.

Referenced by unstructured_to_postcondition(), unstructured_to_total_precondition(), and unstructured_to_transformer().

Here is the call graph for this function:

Here is the caller graph for this function:

unstructured_to_flow_sensitive_postconditions()

transformer unstructured_to_flow_sensitive_postconditions	(	transformer	pre_u,
		transformer	pre,
		unstructured	u
	)

compute pre- and post-conditions in an unstructured from the entry precondition pre and return the exit postcondition.

pre_u is pre filtered by the u's transformer and can be used for any node.

control tail = unstructured_exit(u);

Parameters

pre_u	re_u
pre	re

Definition at line 2040 of file unstructured.c.

{
  transformer post = transformer_undefined;
  list succs = NIL;
  control head = unstructured_control(u);
  /* control tail = unstructured_exit(u); */
 
  forward_control_map_get_blocs(head, &succs);
 
  if(((int)gen_length(succs))>get_int_property("SEMANTICS_MAX_CFG_SIZE1")) {
      semantics_user_warning("\nControl flow graph too large for an accurate analysis (%d nodes)\n"
                        "Have you fully restructured your code?\n", gen_length(succs));
    post = unstructured_to_postconditions(pre, pre_u, u);
  }
  else if(!get_bool_property("SEMANTICS_ANALYZE_UNSTRUCTURED")) {
    semantics_user_warning("\nControl flow graph not analyzed accurately"
                      " because property SEMANTICS_ANALYZE_UNSTRUCTURED is not set\n");
    post = unstructured_to_postconditions(pre_u, pre, u);
  }
  else if(!get_bool_property("SEMANTICS_FIX_POINT")) {
    post = unstructured_to_postconditions(pre_u, pre, u);
  }
  else {
    post = unstructured_to_flow_sensitive_postconditions_or_transformers
      (pre_u, pre, u, true);
  }
  gen_free_list(succs);
 
  pips_assert("Postcondition for unstructured is consistent",
              transformer_consistency_p(post));
 
  return post;
}

References forward_control_map_get_blocs(), gen_free_list(), gen_length(), get_bool_property(), get_int_property(), NIL, pips_assert, semantics_user_warning, transformer_consistency_p(), transformer_undefined, unstructured_control, unstructured_to_flow_sensitive_postconditions_or_transformers(), and unstructured_to_postconditions().

Referenced by unstructured_to_postcondition().

Here is the call graph for this function:

Here is the caller graph for this function:

unstructured_to_flow_sensitive_postconditions_or_transformers()

transformer unstructured_to_flow_sensitive_postconditions_or_transformers	(	transformer	pre_u,
		transformer	pre,
		unstructured	u,
		bool	postcondition_p
	)

compute either the postconditions in an unstructured or the transformer of this unstructured.

In both cases, transformers for all nodes used to be supposed to be available.

Do not go down into nested unstructured

Propagate the precondition in the DAG and recompute the cycle transformers or compute the path transformers and the cycle fix point transformers.

Compute the real precondition for each statement and propagate postconditions in it.

Take care of unreachable nodes

Get rid of the auxiliary data structures

Parameters

pre_u	re_u
pre	precondition at entry: e_pre
u	precondition true for every node: n_pre
postcondition_p	ostcondition_p

Definition at line 1821 of file unstructured.c.

{
  transformer post = transformer_undefined;
  hash_table ancestor_map = hash_table_undefined;
  hash_table scc_map = hash_table_undefined;
  control_mapping fix_point_map  = make_control_fix_point_map();
  unstructured ndu = unstructured_undefined;
  list partition = bourdoncle_partition(u, &ndu, &ancestor_map, &scc_map);
  control_mapping control_postcondition_map = make_control_postcondition_map();
  transformer pre_u_r = transformer_range(pre_u);
  transformer pre_r = transformer_range(pre);
 
  recursive_context context = { postcondition_p, control_postcondition_map };
 
  recursive_context fcontext = { postcondition_p, fix_point_map };
 
  ifdebug(2) {
    pips_debug(2, "Begin for %s with nodes:\n",
               postcondition_p? "postconditions" : "transformer");
    /* Do not go down into nested unstructured */
    gen_multi_recurse(u, statement_domain, gen_false, gen_null,
                      control_domain, gen_true, print_control_node_uns, NULL);
    pips_debug(2, "With entry nodes\n");
    print_control_node_uns(unstructured_control(u));
    pips_debug(2, "And exit node\n");
    print_control_node_uns(unstructured_exit(u));
    pips_debug(2, "And embedding graph:\n");
    gen_multi_recurse(ndu, statement_domain, gen_false, gen_null,
                      control_domain, gen_true, print_control_node_uns, NULL);
  }
 
  /* Propagate the precondition in the DAG and recompute the cycle
     transformers or compute the path transformers and the cycle fix point
     transformers. */
  (void) dag_to_flow_sensitive_postconditions_or_transformers
    (partition, ndu, ancestor_map, scc_map, fix_point_map,
     postcondition_p? pre_u : pre_u_r, postcondition_p? pre : pre_r,
     control_postcondition_map, postcondition_p);
 
  if(postcondition_p) {
    /* Compute the real precondition for each statement and propagate
       postconditions in it. */
 
    dag_to_flow_sensitive_preconditions
    (partition, ndu, ancestor_map, scc_map, fix_point_map, pre_u, pre,
     control_postcondition_map);
  }
 
  /* Take care of unreachable nodes */
  gen_context_multi_recurse(
                            ndu, (void *) & context,
                            statement_domain, gen_false, gen_null,
                            control_domain, gen_true, local_process_unreachable_node,
                            NULL);
 
  ifdebug(2) {
    pips_debug(2, "%s for unstructured\n",
               postcondition_p? "Postconditions": "Path transformer");
    gen_context_multi_recurse(
                              ndu, (void *) & context,
                              statement_domain, gen_false, gen_null,
                              control_domain, gen_true,
                              node_to_path_transformer_or_postcondition,
                              NULL);
    pips_debug(2, "End of map\n");
    if(hash_table_entry_count(fix_point_map)>0) {
      pips_debug(2, "Fix point map:\n");
      gen_context_multi_recurse(
                                u, (void *) & fcontext,
                                statement_domain, gen_false, gen_null,
                                control_domain, gen_true,
                                print_cycle_head_to_fixpoint,
                                NULL);
      pips_debug(2, "End of fix point map\n");
      pips_debug(2, "Dump fix point map %p:\n", fix_point_map);
      HASH_MAP(k, v, {
        control c = (control) k;
        statement s = control_statement(c);
        transformer fp_tf = (transformer) v;
 
        print_control_node_uns(c);
        fprintf(stderr, "Statement %s", statement_identification(s));
        print_transformer(fp_tf);
      }, fix_point_map);
      pips_debug(2, "End of fix point map dump\n");
    }
    else {
      fprintf(stderr, "No fix point. Empty fix point map\n");
    }
  }
 
  post = copy_transformer
    (load_control_postcondition(unstructured_exit(ndu),
                                control_postcondition_map));
  control_postcondition_map = free_control_postcondition_map(control_postcondition_map);
  fix_point_map = free_control_fix_point_map(fix_point_map);
 
  ifdebug(2) {
    pips_assert("The postcondition post is defined", !transformer_undefined_p(post));
    pips_debug(2, "End with unstructured postcondition:\n");
    print_transformer(post);
  }
 
  /* Get rid of the auxiliary data structures */
  bourdoncle_free(ndu, ancestor_map, scc_map);
 
  return post;
}

References bourdoncle_free(), bourdoncle_partition(), control_domain, control_statement, copy_transformer(), dag_to_flow_sensitive_postconditions_or_transformers(), dag_to_flow_sensitive_preconditions(), fprintf(), free_control_fix_point_map(), free_control_postcondition_map(), gen_context_multi_recurse(), gen_false(), gen_multi_recurse(), gen_null(), gen_true(), HASH_MAP, hash_table_entry_count(), hash_table_undefined, ifdebug, load_control_postcondition(), local_process_unreachable_node(), make_control_fix_point_map(), make_control_postcondition_map(), node_to_path_transformer_or_postcondition(), pips_assert, pips_debug, print_control_node_uns(), print_cycle_head_to_fixpoint(), print_transformer, statement_domain, statement_identification(), transformer_range(), transformer_undefined, transformer_undefined_p, unstructured_control, unstructured_exit, and unstructured_undefined.

Referenced by unstructured_to_flow_sensitive_postconditions(), and unstructured_to_transformer().

Here is the call graph for this function:

Here is the caller graph for this function:

unstructured_to_flow_sensitive_total_preconditions()

transformer unstructured_to_flow_sensitive_total_preconditions	(	transformer	t_post_u,
		transformer	pre,
		unstructured	u
	)

control tail = unstructured_exit(u);

Parameters

t_post_u	_post_u
pre	re

Definition at line 2473 of file unstructured.c.

{
  transformer t_pre = transformer_undefined;
  transformer post = transformer_undefined;
  /* control tail = unstructured_exit(u); */
 
  pips_assert("Not implemented yet", false);
  pips_assert("Shut up the compiler", t_post_u==t_post_u && pre==pre && u==u);
 
  pips_assert("Total precondition for unstructured is consistent",
              transformer_consistency_p(t_pre));
 
  return post;
}

References pips_assert, transformer_consistency_p(), and transformer_undefined.

Referenced by unstructured_to_total_precondition().

Here is the call graph for this function:

Here is the caller graph for this function:

unstructured_to_postcondition()

transformer unstructured_to_postcondition	(	transformer	pre,
		unstructured	u,
		transformer	tf
	)

there is only one statement and no arcs in u; no need for a fix-point

FI: pre should not be duplicated because statement_to_postcondition() means that pre is not going to be changed, just post produced.

Do not try anything clever! God knows what may happen in unstructured code. Postcondition post is not computed recursively from its components but directly derived from u's transformer. Preconditions associated to its components are then computed independently, hence the name unstructured_to_postconditionS instead of unstructured_to_postcondition

propagate as precondition an invariant for the whole unstructured u assuming that all nodes in the CFG are fully connected, unless tf is not feasible because the unstructured is never exited or exited thru a call to STOP which invalidates the previous assumption.

FI: I do not know if I should duplicate pre or not.

FI: well, dumdum, you should have duplicated tf!

FI: euh... why? According to comments about transformer_apply() neither arguments are modified...

post = unstructured_to_postconditions(pre_n, pre, u);

Parameters

pre	re
tf	f

Definition at line 2075 of file unstructured.c.

{
    transformer post;
    control c;
 
    pips_debug(8, "begin\n");
 
    pips_assert("unstructured u is defined", u!=unstructured_undefined);
 
    c = unstructured_control(u);
    if(control_predecessors(c) == NIL && control_successors(c) == NIL) {
        /* there is only one statement and no arcs in u; no need for a
           fix-point */
        pips_debug(8, "unique node\n");
        /* FI: pre should not be duplicated because
         * statement_to_postcondition() means that pre is not
         * going to be changed, just post produced.
         */
        post = statement_to_postcondition(transformer_dup(pre),
                                          control_statement(c));
    }
    else {
        /* Do not try anything clever! God knows what may happen in
           unstructured code. Postcondition post is not computed recursively
           from its components but directly derived from u's transformer.
           Preconditions associated to its components are then computed
           independently, hence the name unstructured_to_postconditionS
           instead of unstructured_to_postcondition */
        /* propagate as precondition an invariant for the whole
           unstructured u assuming that all nodes in the CFG are fully
           connected, unless tf is not feasible because the unstructured
           is never exited or exited thru a call to STOP which invalidates
           the previous assumption. */
      transformer tf_u = transformer_undefined;
      transformer pre_n = transformer_undefined;
 
        pips_debug(8, "complex: based on transformer\n");
        if(transformer_empty_p(tf)) {
          tf_u = unstructured_to_flow_insensitive_transformer(u);
        }
        else {
          tf_u = tf;
        }
        pre_n = invariant_wrt_transformer(pre, tf_u);
        ifdebug(8) {
          pips_debug(8, "filtered over approximated precondition holding for any node pre_n:\n");
          (void) print_transformer(pre_n) ;
        }
        /* FI: I do not know if I should duplicate pre or not. */
        /* FI: well, dumdum, you should have duplicated tf! */
        /* FI: euh... why? According to comments about transformer_apply()
         * neither arguments are modified...
         */
        /* post = unstructured_to_postconditions(pre_n, pre, u); */
        post = unstructured_to_flow_sensitive_postconditions(pre, pre_n, u);
        pips_assert("A valid postcondition is returned",
                    !transformer_undefined_p(post));
        if(transformer_undefined_p(post)) {
          post = transformer_apply(transformer_dup(tf), pre);
        }
        transformer_free(pre_n);
    }
 
    pips_debug(8, "end\n");
 
    return post;
}

References control_predecessors, control_statement, control_successors, ifdebug, invariant_wrt_transformer(), NIL, pips_assert, pips_debug, print_transformer, statement_to_postcondition(), transformer_apply(), transformer_dup(), transformer_empty_p(), transformer_free(), transformer_undefined, transformer_undefined_p, unstructured_control, unstructured_to_flow_insensitive_transformer(), unstructured_to_flow_sensitive_postconditions(), and unstructured_undefined.

Referenced by instruction_to_postcondition().

Here is the call graph for this function:

Here is the caller graph for this function:

unstructured_to_postconditions()

static transformer unstructured_to_postconditions ( transformer  pre, transformer  pre_first, unstructured  u  )

static

SHARING! Every statement gets a pointer to the same precondition! I do not know if it's good or not but beware the bugs!!!

FI: changed to make free_transformer_mapping possible without testing sharing.

pre and pre_first can or not be used depending on the unstructured structure. They are always duplicated and the caller has to take care of their de-allocation.

special case for the first node if it has no predecessor

and if it is a test, as it always should, at least if

unspaghettify has been applied...

this is pretty useless and should be generalized to the DAG part of the CFG

refine the precondition if the node has only one predecessor and if this predecessor is a test and if the test can be exploited

the condition is true if c is the first successor of prev_c

Parameters

pre_first	precondition holding for any node
u	precondition holding at entry

Definition at line 1952 of file unstructured.c.

{
  list nodes = NIL ;
  control entry_node = unstructured_control(u) ;
  control exit_node = unstructured_exit(u) ;
  transformer c_pre = transformer_undefined;
  transformer post = transformer_undefined;
  transformer exit_post = transformer_undefined;
 
  pips_debug(8, "begin\n");
 
  /* SHARING! Every statement gets a pointer to the same precondition!
   * I do not know if it's good or not but beware the bugs!!!
   */
  /* FI: changed to make free_transformer_mapping possible without 
   * testing sharing.
   *
   * pre and pre_first can or not be used depending on the
   * unstructured structure. They are always duplicated and
   * the caller has to take care of their de-allocation.
   */
  CONTROL_MAP(c, {
    statement st = control_statement(c) ;
    if(c==entry_node && ENDP(control_predecessors(c)) && statement_test_p(st)) {
      /* special case for the first node if it has no predecessor */
      /* and if it is a test, as it always should, at least if */
      /* unspaghettify has been applied... */
      /* this is pretty useless and should be generalized to the
         DAG part of the CFG */
      c_pre = transformer_dup(pre_first);
      post = statement_to_postcondition(c_pre, st);
      transformer_free(post);
    }
    else {
      transformer c_pre_m = transformer_undefined;
 
      c_pre = transformer_dup(pre);
      c_pre_m = c_pre;
 
      /* refine the precondition if the node has only one
         predecessor and if this predecessor is a test and if the
         test can be exploited */
      if(gen_length(control_predecessors(c))==1 && c!=entry_node) {
        control prev_c = CONTROL(CAR(control_predecessors(c)));
        statement prev_st = control_statement(prev_c);
 
        if(statement_test_p(prev_st)) {
          /* the condition is true if c is the first successor of prev_c */
          bool true_false = (c==(CONTROL(CAR(control_successors(prev_c)))));
          expression e = test_condition(statement_test(prev_st));
          transformer context = transformer_range(pre);
 
          c_pre_m = precondition_add_condition_information(c_pre, e, context, true_false);
          free_transformer(context);
        }
      }
 
      post = statement_to_postcondition(c_pre_m, st);
      if(c==exit_node) {
        exit_post = post;
      }
      else {
        transformer_free(post);
      }
    }
  }, entry_node, nodes);
 
  gen_free_list(nodes) ;
 
  if(transformer_undefined_p(exit_post)) {
    exit_post = transformer_empty();
  }
 
  ifdebug(8) {
    pips_debug(8, "exit postcondition:\n");
    (void) print_transformer(exit_post) ;
  }
  pips_debug(8, "end\n");
 
  return exit_post;
}

References CAR, CONTROL, CONTROL_MAP, control_predecessors, control_statement, control_successors, ENDP, free_transformer(), gen_free_list(), gen_length(), ifdebug, NIL, pips_debug, precondition_add_condition_information(), print_transformer, statement_test(), statement_test_p(), statement_to_postcondition(), test_condition, transformer_dup(), transformer_empty(), transformer_free(), transformer_range(), transformer_undefined, transformer_undefined_p, unstructured_control, and unstructured_exit.

Referenced by unstructured_to_flow_sensitive_postconditions().

Here is the call graph for this function:

Here is the caller graph for this function:

unstructured_to_transformer()

transformer unstructured_to_transformer	(	unstructured	u,
		transformer	e_pre,
		list	e
	)

effects of u

approximate store condition for all control nodes: simple context for improved transformer derivation; it is not a precondition and should have no arguments.

Same as previous one for the store on entry in the unstructured. This the entry node usually has predecessors in the CFG, this is not the context for the entry node. It is not a precondition.

No information available on entrance

Cheapest fix point transformer. The flow insensitive fix point could be used instead.

pre is replaced by its range condition later when needed

Transformers should be computed precisely whether the unstructured is left by the exit node or by an explicit or implicit call to STOP.

computing the transformer for u is like computing the postcondition with no information on entry: no, the input context may be used to refine the transformer.

pre_u is restricted to its range later when needed.

These tests should be performed at the scc level

Not really linked to fix point issue, but a way to know we are using a FAST option.

Do something for nodes unreachable from the entry but linked to the exit

The control flow graph is never exited... by the exit node

The unstructured is never exited, but all nodes are supposed to have transformers. This would never occur if the control restructuration were clean unless an infinite loop is stopped within a called procedure. Control effects are not reported.

FI: pre should be used!

Might be useless because it's now performed just above and more generally by a gen_multi_recurse()

Parameters

e_pre	_pre
e	precondition on entrance

Definition at line 2332 of file unstructured.c.

{
  transformer tf = transformer_undefined;
  list succs = NIL;
  control head = unstructured_control(u);
  control tail = unstructured_exit(u);
  /* approximate store condition for all control nodes: simple context for
     improved transformer derivation; it is not a precondition and should have no
     arguments. */
  transformer pre = transformer_undefined;
  /* Same as previous one for the store on entry in the unstructured. This
     the entry node usually has predecessors in the CFG, this is not the
     context for the entry node. It is not a precondition. */
  transformer pre_u = transformer_undefined;
 
  if(transformer_undefined_p(e_pre)) {
    /* No information available on entrance */
    pre = transformer_identity();
  }
  else {
    /* Cheapest fix point transformer. The flow insensitive fix point
       could be used instead. */
    transformer fpf = effects_to_transformer(e);
 
    /* pre is replaced by its range condition later when needed*/
    pre = transformer_safe_apply(fpf, e_pre);
    free_transformer(fpf);
  }
 
  pips_debug(8,"begin\n");
 
  forward_control_map_get_blocs(head, &succs);
 
  /* Transformers should be computed precisely whether the unstructured is
     left by the exit node or by an explicit or implicit call to STOP. */
  if(true || gen_in_list_p(tail, succs)) {
    /* computing the transformer for u is like computing the postcondition
       with no information on entry: no, the input context may be used to
       refine the transformer. */
 
    if(transformer_undefined_p(e_pre)) {
      pre_u = transformer_identity();
    }
    else {
      /* pre_u is restricted to its range later when needed. */
      pre_u = transformer_dup(e_pre);
    }
 
    /* These tests should be performed at the scc level */
    if(((int)gen_length(succs))>get_int_property("SEMANTICS_MAX_CFG_SIZE2")) {
      semantics_user_warning("\nControl flow graph too large for any analysis (%d nodes)\n"
                        "Have you fully restructured your code?\n", gen_length(succs));
      unstructured_to_transformers(u, pre);
 
      if(!gen_in_list_p(tail, succs)) {
        tf = transformer_empty();
      }
      else {
        tf = effects_to_transformer(e);
      }
    }
    else if(((int)gen_length(succs))>get_int_property("SEMANTICS_MAX_CFG_SIZE1")) {
      semantics_user_warning("\nControl flow graph too large for an accurate analysis (%d nodes)\n"
                        "Have you fully restructured your code?\n", gen_length(succs));
      unstructured_to_transformers(u, pre);
 
      if(!gen_in_list_p(tail, succs)) {
        tf = transformer_empty();
      }
      else {
        tf = unstructured_to_flow_insensitive_transformer(u);
      }
    }
    else if(!get_bool_property("SEMANTICS_ANALYZE_UNSTRUCTURED")) {
      semantics_user_warning("\nControl flow graph not analyzed accurately"
                        " because property SEMANTICS_ANALYZE_UNSTRUCTURED is not set\n");
      unstructured_to_transformers(u, pre);
 
      if(!gen_in_list_p(tail, succs)) {
        tf = transformer_empty();
      }
      else {
        tf = unstructured_to_flow_insensitive_transformer(u);
      }
    }
    else if(!get_bool_property("SEMANTICS_FIX_POINT")) {
      /* Not really linked to fix point issue, but a way to know we are
         using a FAST option. */
      unstructured_to_transformers(u, pre);
 
      if(!gen_in_list_p(tail, succs)) {
        tf = transformer_empty();
      }
      else {
        tf = unstructured_to_flow_insensitive_transformer(u);
      }
    }
    else {
      tf = unstructured_to_flow_sensitive_postconditions_or_transformers
        (pre_u, pre, u, false);
    }
    free_transformer(pre_u);
  }
 
  if(!gen_in_list_p(tail, succs)) {
  /* Do something for nodes unreachable from the entry but linked to the exit */
    /* The control flow graph is never exited... by the exit node */
    /* The unstructured is never exited, but all nodes are supposed to
       have transformers. This would never occur if the control
       restructuration were clean unless an infinite loop is stopped
       within a called procedure. Control effects are not reported. */
    /* FI: pre should be used! */
    gen_multi_recurse(
                      u,
                      statement_domain, gen_false, gen_null,
                      control_domain, gen_true, unreachable_node_to_transformer,
                      NULL);
  }
 
  /* Might be useless because it's now performed just above and more
     generally by a gen_multi_recurse() */
  if(!gen_in_list_p(tail, succs)) {
    pips_assert("if exit is not reached, tf is empty", transformer_empty_p(tf));
    tf = transformer_empty();
  }
 
  gen_free_list(succs);
  free_transformer(pre);
 
  pips_debug(8,"end\n");
 
  return tf;
}

References control_domain, effects_to_transformer(), forward_control_map_get_blocs(), free_transformer(), gen_false(), gen_free_list(), gen_in_list_p(), gen_length(), gen_multi_recurse(), gen_null(), gen_true(), get_bool_property(), get_int_property(), NIL, pips_assert, pips_debug, semantics_user_warning, statement_domain, transformer_dup(), transformer_empty(), transformer_empty_p(), transformer_identity(), transformer_safe_apply(), transformer_undefined, transformer_undefined_p, unreachable_node_to_transformer(), unstructured_control, unstructured_exit, unstructured_to_flow_insensitive_transformer(), unstructured_to_flow_sensitive_postconditions_or_transformers(), and unstructured_to_transformers().

Referenced by instruction_to_transformer().

Here is the call graph for this function:

Here is the caller graph for this function:

unstructured_to_transformers()

static void unstructured_to_transformers ( unstructured  u, transformer  pre  )

static

Computation of transformers associated to each node of u and to each of its sub-statements.

pre is valid for any node of u

There is no need to compute transformers for unreachable code, using CONTROL_MAP, but this may create storage and prettyprinter problems because of the data structure inconsistency.

Definition at line 2309 of file unstructured.c.

{
  list blocs = NIL ;
  control ct = unstructured_control(u) ;
 
  pips_debug(5,"begin\n");
 
  /* There is no need to compute transformers for unreachable code,
   * using CONTROL_MAP, but this may create storage and prettyprinter
   * problems because of the data structure inconsistency.
   */
  CONTROL_MAP(c, {
    statement st = control_statement(c) ;
    (void) statement_to_transformer(st, pre) ;
  }, ct, blocs) ;
 
  gen_free_list(blocs) ;
 
  pips_debug(5,"end\n");
}

References CONTROL_MAP, control_statement, gen_free_list(), NIL, pips_debug, statement_to_transformer(), and unstructured_control.

Referenced by unstructured_to_transformer().

Here is the call graph for this function:

Here is the caller graph for this function:

update_control_postcondition()

static void update_control_postcondition ( control  c, transformer  post, control_mapping  control_postcondition_map  )

static

Definition at line 268 of file unstructured.c.

{
  statement stat = control_statement(c);
 
  pips_assert("The statement is defined",
              !meaningless_control_p(c) && !statement_undefined_p(stat));
  pips_assert("The postcondition is already defined", 
              hash_get((hash_table) control_postcondition_map, (void *) c)
              != HASH_UNDEFINED_VALUE);
 
  ifdebug(6) {
    transformer old_post = hash_get((hash_table) control_postcondition_map,
                                    (void *) c);
    pips_debug(6, "Update postcondition for control %p and statement %s:\n",
               c, statement_identification(stat));
    pips_debug(6, "Old postcondition:\n");
    print_transformer(old_post);
    pips_debug(6, "New postcondition:\n");
    print_transformer(post);
  }
 
  hash_update((hash_table) (control_postcondition_map),
              (void *)c, (void *) post);
}

References control_statement, hash_get(), HASH_UNDEFINED_VALUE, hash_update(), ifdebug, meaningless_control_p(), pips_assert, pips_debug, print_transformer, statement_identification(), and statement_undefined_p.

Referenced by cycle_to_flow_sensitive_preconditions().

Here is the call graph for this function:

Here is the caller graph for this function:

update_cycle_temporary_precondition()

void update_cycle_temporary_precondition	(	control	c,
		transformer	pre,
		control_mapping	cycle_temporary_precondition_map
	)

Parameters

pre	re
cycle_temporary_precondition_map	ycle_temporary_precondition_map

Definition at line 1021 of file unstructured.c.

{
  statement s = control_statement(c);
 
  pips_debug(2, "For control %p with statement %s:\n", c, statement_identification(s));
  update_temporary_precondition
    ((void *) c, pre, (hash_table) cycle_temporary_precondition_map);
 
  ifdebug(6) {
    pips_debug(6, "Precondition %p for cycle %p:\n", pre, c);
    print_transformer(pre);
  }
}

References control_statement, ifdebug, pips_debug, print_transformer, statement_identification(), and update_temporary_precondition().

Referenced by cycle_to_flow_sensitive_preconditions(), and dag_to_flow_sensitive_preconditions().

Here is the call graph for this function:

Here is the caller graph for this function:

update_statement_temporary_precondition()

void update_statement_temporary_precondition	(	statement	s,
		transformer	pre,
		statement_mapping	statement_temporary_precondition_map
	)

Parameters

pre	re
statement_temporary_precondition_map	tatement_temporary_precondition_map

Definition at line 997 of file unstructured.c.

{
  pips_debug(2, "For statement %s:\n", statement_identification(s));
  update_temporary_precondition
    ((void *) s, pre, (hash_table) statement_temporary_precondition_map);
}

References pips_debug, statement_identification(), and update_temporary_precondition().

Referenced by cycle_to_flow_sensitive_preconditions(), and dag_to_flow_sensitive_preconditions().

Here is the call graph for this function:

Here is the caller graph for this function:

update_temporary_precondition()

void update_temporary_precondition	(	void *	k,
		transformer	pre,
		hash_table	precondition_map
	)

Parameters

pre	re
precondition_map	recondition_map

Definition at line 975 of file unstructured.c.

{
  transformer t_pre = (transformer) hash_get(precondition_map, k);
 
  if(t_pre == (transformer) HASH_UNDEFINED_VALUE) {
    pips_debug(2, "No previous precondition. Current one %p:\n", pre);
    ifdebug(2) print_transformer(pre);
    hash_put(precondition_map, k, (void *) transformer_dup(pre));
  }
  else {
    transformer n_t_pre = transformer_convex_hull(pre, t_pre);
    hash_update(precondition_map, k, (void *) n_t_pre);
    pips_debug(2, "Previous precondition %p:\n", t_pre);
    ifdebug(2) print_transformer(t_pre);
    pips_debug(2, "New precondition %p:\n", n_t_pre);
    ifdebug(2) print_transformer(n_t_pre);
    free_transformer(t_pre);
  }
}

References free_transformer(), hash_get(), hash_put(), HASH_UNDEFINED_VALUE, hash_update(), ifdebug, pips_debug, print_transformer, transformer_convex_hull(), and transformer_dup().

Referenced by update_cycle_temporary_precondition(), and update_statement_temporary_precondition().

Here is the call graph for this function:

Here is the caller graph for this function: