PIPS
|
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "linear.h"
#include "genC.h"
#include "ri.h"
#include "effects.h"
#include "graph.h"
#include "dg.h"
#include "misc.h"
#include "properties.h"
#include "ri-util.h"
#include "effects-util.h"
#include "ricedg.h"
#include "effects-generic.h"
#include "effects-simple.h"
#include "chains.h"
#include "pipsdbm.h"
#include "pips-libs.h"
Go to the source code of this file.
Macros | |
#define | MAKE_STATEMENT_SET() (set_make( set_pointer )) |
Macro to create set. More... | |
#define | INIT_STATEMENT_SIZE 20 |
Default sizes for corresponding sets. More... | |
#define | INIT_ENTITY_SIZE 10 |
#define | GEN(st) ((set)hash_get( Gen, (char *)st )) |
#define | REF(st) ((set)hash_get( Ref, (char *)st )) |
#define | DEF_IN(st) ((set)hash_get(Def_in, (char *)st)) |
#define | DEF_OUT(st) ((set)hash_get(Def_out, (char *)st)) |
#define | REF_IN(st) ((set)hash_get(Ref_in, (char *)st)) |
#define | REF_OUT(st) ((set)hash_get(Ref_out, (char *)st)) |
#define | TABLE_FREE(t) {HASH_MAP( k, v, {set_free( (set)v ) ;}, t ) ; hash_table_free(t);} |
Typedefs | |
typedef void * | arc_label |
– usedef.c More... | |
typedef void * | vertex_label |
Functions | |
static void | reset_effects () |
Some forward declarations. More... | |
static list | load_statement_effects (statement s) |
static void | inout_control () |
static void | inout_statement () |
static void | genref_statement () |
static bool | dd_du (effect fin, effect fout) |
DD_DU detects Def/Def, Def/Use conflicts between effects FIN and FOUT. More... | |
static bool | ud (effect fin, effect fout) |
UD detects Use/Def conflicts between effects FIN and FOUT. More... | |
static void | add_conflicts (effect fin, statement stout, vertex vout, cons *effect_outs, bool(*which)()) |
adds conflict arcs to the dependence graph dg between the in-coming statement STIN and the out-going STOUT. More... | |
static void | local_print_statement_set (string msg, set s) |
Access functions for debug only. More... | |
static vertex | vertex_statement (statement st) |
static bool | init_one_statement (statement st) |
Initializes the global data structures needed for usedef computation of one statement. More... | |
static void | kill_effects (set gen, set killers) |
The genref_xxx functions implement the computation of GEN and REF sets from Aho, Sethi and Ullman "Compilers" (p. More... | |
static void | genref_one_statement (statement st) |
Compute Gen and Ref set for a single statement. More... | |
static void | genref_test (test t, statement s) |
Compute Gen and Ref set for a test. More... | |
static void | mask_effects (set s, list l) |
MASK_EFFECTS masks the effects in S according to the locals L. More... | |
static void | genref_any_loop (statement body, statement st, list locals, _UNUSED_ bool one_trip_do_p) |
Compute Gen and Ref set for any loop (do, for, while,...) @description It has to deal specially with the loop variable which is not managed in the Dragon book. More... | |
static void | genref_loop (loop l, statement st) |
Compute Gen and Ref set for a "do" loop @description see genref_any_loop() More... | |
static void | genref_forloop (forloop l, statement st) |
Compute Gen and Ref set for a "for" loop @description see genref_any_loop() More... | |
static void | genref_whileloop (whileloop l, statement st) |
Compute Gen and Ref set for a "while" loop @description see genref_any_loop() More... | |
static void | genref_block (cons *sts, statement st) |
Compute Gen and Ref set for a block @description The Dragon book only deals with a sequence of two statements. More... | |
static void | genref_unstructured (unstructured u, statement st) |
Compute Gen and Ref set for an unstructured @description computes the gens, refs, and kills set of the unstructured by recursing on INOUT_CONTROL. More... | |
static void | genref_instruction (instruction i, statement st) |
Does the dispatch and recursion loop @description. More... | |
static void | genref_statement (statement s) |
Compute recursively Gen and Ref set for a statement. More... | |
static void | inout_block (_UNUSED_ statement st, cons *sts) |
Propagates in sets of ST (which is inherited) to compute the out sets. More... | |
static void | inout_test (_UNUSED_ statement s, test t) |
Propagates in sets of ST (which is inherited) to compute the out sets. More... | |
static void | inout_any_loop (statement st, statement body, bool one_trip_do_p, bool __attribute__((unused)) never_executed_p) |
Propagates in sets of ST (which is inherited) to compute the out sets. More... | |
static void | inout_loop (statement st, loop lo) |
Propagates in sets of ST (which is inherited) to compute the out sets. More... | |
static void | inout_whileloop (statement st, whileloop wl) |
Propagates in sets of ST (which is inherited) to compute the out sets. More... | |
static void | inout_forloop (statement st, forloop fl) |
Propagates in sets of ST (which is inherited) to compute the out sets. More... | |
static void | inout_call (statement st, call __attribute__((unused)) c) |
Propagates in sets of ST (which is inherited) to compute the out sets. More... | |
static void | inout_unstructured (statement st, unstructured u) |
Propagates in sets of ST (which is inherited) to compute the out sets. More... | |
static void | inout_statement (statement st) |
Propagates in sets of ST (which is inherited) to compute the out sets. More... | |
static void | inout_control (control ct) |
Propagates in sets of ST (which is inherited) to compute the out sets. More... | |
static cons * | pushnew_conflict (effect fin, effect fout, cons *cfs) |
adds the conflict FIN->FOUT in the list CFS @description adds the conflict FIN->FOUT in the list CFS (if it's not already there, and apparently even if it's already there for performance reason...). More... | |
graph | statement_dependence_graph (statement s) |
Compute from a given statement, the dependency graph. More... | |
static void | set_effects (char *module_name, enum chain_type use) |
Select the type of effects used to compute dependence chains. More... | |
static bool | chains (char *module_name, enum chain_type use) |
Compute chain dependence for a module according different kinds of store-like effects. More... | |
bool | atomic_chains (const string module_name) |
Phase to compute atomic chains based on proper effects (simple memory accesses) More... | |
bool | region_chains (const string module_name) |
Phase to compute atomic chains based on array regions. More... | |
bool | in_out_regions_chains (const string module_name) |
Phase to compute atomic chains based on in-out array regions. More... | |
Variables | |
static hash_table | effects2statement |
Mapping from effects to the associated statement. More... | |
static hash_table | Gen |
Gen maps each statement to the effects it generates. More... | |
static hash_table | Ref |
Refs maps each statement to the effects it references. More... | |
static set | current_defs |
current_defs is the set of DEF at the current point of the computation More... | |
static set | current_refs |
static hash_table | Def_in |
Def_in maps each statement to the statements that are in-coming the statement It's only used for unstructured, current_defs is used for structured parts. More... | |
static hash_table | Def_out |
Def_out maps each statement to the statements that are out-coming the statement It's only used for unstructured, current_defs is used for structured parts. More... | |
static hash_table | Ref_in |
Ref_in maps each statement to the effects that are in-coming the statement It's only used for unstructured, current_refs is used for structured parts. More... | |
static hash_table | Ref_out |
Ref_out maps each statement to the effects that are out-coming the statement It's only used for unstructured, current_refs is used for structured parts. More... | |
static graph | dg |
dg is the dependency graph ; FIXME : should not be static global ? More... | |
static hash_table | Vertex_statement |
Vertex_statement maps each statement to its vertex in the dependency graph. More... | |
static bool | one_trip_do_p |
Some properties. More... | |
static bool | keep_read_read_dependences_p |
static bool | mask_effects_p |
static bool | dataflow_dependence_only_p |
static bool | rgch = false |
functions for effects maps More... | |
static bool | iorgch = false |
#define INIT_STATEMENT_SIZE 20 |
#define MAKE_STATEMENT_SET | ( | ) | (set_make( set_pointer )) |
#define TABLE_FREE | ( | t | ) | {HASH_MAP( k, v, {set_free( (set)v ) ;}, t ) ; hash_table_free(t);} |
typedef void* arc_label |
typedef void* vertex_label |
|
static |
adds conflict arcs to the dependence graph dg between the in-coming statement STIN and the out-going STOUT.
@description Note that output dependencies are not minimal (e.g., i = s ; s = ... ; s = ...) creates an oo-dep between the i assignment and the last s assignment.
To speed up pushnew_conflict() without damaging the integrity of the use-def chains
I think that most of this is hazardous when mixes of pointers, arrays and structs are involved. However, there should be no pointer anymore with CONSTANT_PATH_EFFECTS set to TRUE! We need to think more about all of this. BC.
Second version due to accuracy improvements in effect computation
This is the standard case
I'm not sure this can be the case because of effects_might_conflict_even_read_only_p(fin, fout)
a write on the shorter memory access path conflicts with the longer one. If a[i] is written, then a[i][j] depends on it. If a[i] is read, no conflict
dout > din
same explanation as above
Why should we limit this test to pointers? Structures, structures of arrays and arrays of structures with pointers embedded somewhere must behave in the very same way. Why not unify the two cases? Because we have not spent enough time thinking about memory access paths.
a write on the shorter memory access path conflicts with the longer one. If a[i] is written, then a[i][j] depends on it. If a[i] is read, no conflict
same explanation as above
Here we filter effect on loop indices except for abstract locations
Add conflicts
The sink vertex in the graph
Try first to find an existing vertex for this statement
There is no sink vertex for this statement, create one
Use existing vertex for this statement
Definition at line 1050 of file chains.c.
References abstract_locations_may_conflict_p(), action_write_p, bool_to_string(), CONS, EFFECT, effect_action, effect_any_reference, effect_entity(), effect_to_entity(), effects2statement, effects_might_conflict_even_read_only_p(), ENDP, entities_may_conflict_p(), entity_abstract_location_p(), entity_local_name(), entity_name, entity_type, FOREACH, fprintf(), gen_length(), gen_nconc(), gen_once_p(), hash_get(), ifdebug, load_statement_effects(), load_statement_enclosing_loops(), loop_index, loops, make_dg_arc_label(), make_successor(), NIL, ORDERING_NUMBER, ORDERING_STATEMENT, pips_debug, pips_internal_error, pointer_type_p(), print_effect, pushnew_conflict(), reference_indices, statement_loop(), statement_number, statement_ordering, store_effect_p(), SUCCESSOR, successor_arc_label, successor_undefined, successor_undefined_p, successor_vertex, ud(), ultimate_type(), variable_to_abstract_location(), vertex_statement(), and vertex_successors.
Referenced by inout_statement().
Phase to compute atomic chains based on proper effects (simple memory accesses)
module_name | odule_name |
Definition at line 1442 of file chains.c.
References chains(), module_name(), and USE_PROPER_EFFECTS.
|
static |
Compute chain dependence for a module according different kinds of store-like effects.
module_name | is the name of the module we want to compute the chains |
use | the type of effects we want to use to compute the dependence chains |
set_entity_to_size(); should be performed at the workspace level
Definition at line 1397 of file chains.c.
References clean_enclosing_loops(), db_get_memory_resource(), DB_PUT_MEMORY_RESOURCE, debug_off, debug_on, get_current_module_statement(), ifdebug, local_name_to_top_level_entity(), loops_mapping_of_statement(), module_name(), pips_debug, prettyprint_dependence_graph(), reset_current_module_entity(), reset_current_module_statement(), reset_effects(), reset_ordering_to_statement(), set_conflict_testing_properties(), set_current_module_entity(), set_current_module_statement(), set_effects(), set_enclosing_loops_map(), set_ordering_to_statement(), and statement_dependence_graph().
Referenced by atomic_chains(), compute_dg_on_statement_from_chains(), compute_dg_on_statement_from_chains_in_place(), do_simplify_dg(), in_out_regions_chains(), region_chains(), and rice_dependence_graph().
DD_DU detects Def/Def, Def/Use conflicts between effects FIN and FOUT.
Definition at line 1025 of file chains.c.
References action_read_p, action_write_p, dataflow_dependence_only_p, and effect_action.
Referenced by inout_statement().
|
static |
Compute Gen and Ref set for any loop (do, for, while,...) @description It has to deal specially with the loop variable which is not managed in the Dragon book.
Effect masking is performed on locals (i.e., gen&ref sets are pruned from local definitions).
For DO loop, if loops are at least one trip (set by property "ONE_TRIP_DO"), then statements are always killed by execution of loop body.
l | the loop to compute |
st | the statement that hold the loop |
Compute genref on the loop body
Summarize the body to the statement that hold the loop
Filter effects on local variables
Definition at line 372 of file chains.c.
References gen(), GEN, genref_statement(), mask_effects(), mask_effects_p, REF, ref, and set_union().
Referenced by genref_forloop(), genref_loop(), and genref_whileloop().
Compute Gen and Ref set for a block @description The Dragon book only deals with a sequence of two statements.
here we generalize to lists, via recursion. Statement are processed in reversed order (i.e. on the descending phase of recursion)
sts | the list of statements inside the block |
st | the statement that hold the block |
Summarize for the block
loop over statements inside the block
Definition at line 460 of file chains.c.
References FOREACH, GEN, genref_statement(), kill_effects(), mask_effects(), mask_effects_p, REF, set_union(), and statement_declarations.
Referenced by genref_instruction().
Compute Gen and Ref set for a "for" loop @description see genref_any_loop()
l | the loop to compute |
st | the statement that hold the loop |
Call the generic function handling all kind of loop
Definition at line 426 of file chains.c.
References forloop_body, genref_any_loop(), one_trip_do_p, and statement_declarations.
Referenced by genref_instruction().
|
static |
Does the dispatch and recursion loop @description.
i | is the instruction |
st | is the statement that hold the instruction |
no recursion for these kind of instruction
Definition at line 530 of file chains.c.
References genref_block(), genref_forloop(), genref_loop(), genref_test(), genref_unstructured(), genref_whileloop(), instruction_block, instruction_forloop, instruction_loop, instruction_tag, instruction_test, instruction_unstructured, instruction_whileloop, is_instruction_block, is_instruction_call, is_instruction_expression, is_instruction_forloop, is_instruction_goto, is_instruction_loop, is_instruction_test, is_instruction_unstructured, is_instruction_whileloop, and pips_internal_error.
Referenced by genref_statement().
Compute Gen and Ref set for a "do" loop @description see genref_any_loop()
l | the loop to compute |
st | the statement that hold the loop |
Building locals list
Call the generic function handling all kind of loop
We free because we are good programmers and we don't leak ;-)
Definition at line 403 of file chains.c.
References gen_copy_seq(), gen_free_list(), gen_nconc(), genref_any_loop(), loop_body, loop_locals, one_trip_do_p, and statement_declarations.
Referenced by genref_instruction().
|
static |
Compute Gen and Ref set for a single statement.
st | the statement to compute |
Loop over effects to find which one will generates or references some variables
A write effect will always generate a definition
A read effect will always generate a reference
Secure programming
Definition at line 276 of file chains.c.
References action_read_p, action_write_p, effect_action, effects2statement, FOREACH, gen(), GEN, hash_get(), load_statement_effects(), pips_assert, pips_internal_error, REF, ref, set_add_element(), and set_clear().
Referenced by genref_statement().
|
static |
Referenced by genref_any_loop(), genref_block(), genref_test(), genref_unstructured(), and statement_dependence_graph().
|
static |
Compute recursively Gen and Ref set for a statement.
This is the main entry to this task. @description computes the gens and refs set of the statement by recursing
s | is the statement to compute |
Compute genref using effects associated to the statement itself
Recurse inside the statement (relevant for blocks, loop, ...)
Definition at line 578 of file chains.c.
References debug(), GEN, genref_instruction(), genref_one_statement(), ifdebug, local_print_statement_set(), REF, statement_identification(), and statement_instruction.
Compute Gen and Ref set for a test.
t | the test |
s | the statement to compute |
compute true path
compute false path
Combine the two path to summarize the test
Definition at line 310 of file chains.c.
References GEN, genref_statement(), REF, ref, set_union(), test_false, and test_true.
Referenced by genref_instruction().
|
static |
Compute Gen and Ref set for an unstructured @description computes the gens, refs, and kills set of the unstructured by recursing on INOUT_CONTROL.
The gens&refs can then be inferred. The situation for the kills is more fishy; for the moment, we just keep the kills that are common to all statements of the control graph.
u | is the unstructured |
st | is the statement that hold the unstructured |
recursing
Definition at line 494 of file chains.c.
References CONTROL_MAP, control_statement, DEF_IN, DEF_OUT, empty, exit, GEN, gen_free_list(), genref_statement(), MAKE_STATEMENT_SET, NIL, REF, ref, REF_IN, REF_OUT, set_assign(), set_clear(), set_difference(), set_free(), set_undefined_p, set_union(), unstructured_control, and unstructured_exit.
Referenced by genref_instruction().
Compute Gen and Ref set for a "while" loop @description see genref_any_loop()
l | the loop to compute |
st | the statement that hold the loop |
Call the generic function handling all kind of loop
Definition at line 442 of file chains.c.
References genref_any_loop(), one_trip_do_p, statement_declarations, and whileloop_body.
Referenced by genref_instruction().
Phase to compute atomic chains based on in-out array regions.
module_name | odule_name |
Definition at line 1456 of file chains.c.
References chains(), module_name(), and USE_IN_OUT_REGIONS.
Initializes the global data structures needed for usedef computation of one statement.
st | the statement to initialize |
First initialization (normal use)
Create a new vertex in the DG for the statement:
If the statement has never been seen, allocate new sets: This could be optimized : {DEF,REF}_{IN,OUT} are needed only for unstructured
FI: regions are not really proper effects... I should use proper effects for non-call instruction I need a global variable let's kludge this for the time being, 5 August 1992
If the statement has already been seen, reset the sets associated to it:
Go on recursing down:
Definition at line 172 of file chains.c.
References CONS, Def_in, DEF_IN, Def_out, DEF_OUT, dg, EFFECT, effects2statement, FOREACH, fprintf(), Gen, GEN, graph_vertices, hash_put(), HASH_UNDEFINED_VALUE, ifdebug, instruction_block_p, load_statement_effects(), make_dg_vertex_label(), MAKE_STATEMENT_SET, make_vertex(), NIL, print_effects, Ref, REF, Ref_in, REF_IN, Ref_out, REF_OUT, sccflags_undefined, set_clear(), statement_instruction, statement_number, statement_ordering, VERTEX, and Vertex_statement.
Referenced by statement_dependence_graph().
|
static |
Propagates in sets of ST (which is inherited) to compute the out sets.
st | is the statement that hold the loop |
lo | is the loop |
one_trip_do_p | tell if there is always at least one trip (do loop only) |
never_executed_p | tell if loop never executed (when it's possible, do loop only) (unused) |
Compute "in" sets for the loop body
Compute loop body
Compute "out" sets for the loop
Body is not always done, approximation by union
Definition at line 673 of file chains.c.
References current_defs, current_refs, GEN, inout_statement(), one_trip_do_p, REF, set_dup(), set_free(), and set_union().
Referenced by inout_forloop(), inout_loop(), and inout_whileloop().
Propagates in sets of ST (which is inherited) to compute the out sets.
st | is the statement that hold the block |
sts | is the list of statement inside the block |
loop over statements inside the block
Compute the outs from the ins for this statement
Definition at line 614 of file chains.c.
References FOREACH, and inout_statement().
Referenced by inout_statement().
|
static |
Propagates in sets of ST (which is inherited) to compute the out sets.
st | is the statement that hold the call |
c | is the call (unused) |
Compute "out" sets
Definition at line 746 of file chains.c.
References current_defs, current_refs, GEN, kill_effects(), REF, and set_union().
Referenced by inout_statement().
|
static |
|
static |
Propagates in sets of ST (which is inherited) to compute the out sets.
@description It computes the in and out sets of the structured control graph. This is done by fixed point iteration (see Dragon book, p. 625), except that the in set of CT is not empty (this explains the set_union instead of set_assign in the fixed point computation loop on IN( st )). Once again, the correctness of this modification is not proven.
ct | is the control to compute |
Prepare "in" sets
Restore out sets
Definition at line 909 of file chains.c.
References CAR, CONTROL, CONTROL_MAP, control_predecessors, control_statement, current_defs, current_refs, DEF_IN, DEF_OUT, fprintf(), GEN, gen_free_list(), ifdebug, inout_statement(), local_print_statement_set(), MAKE_STATEMENT_SET, MAPL, NIL, REF, REF_IN, REF_OUT, set_assign(), set_clear(), set_equal_p(), set_free(), and set_union().
Propagates in sets of ST (which is inherited) to compute the out sets.
st | is the statement that hold the loop |
t | is the loop |
Definition at line 735 of file chains.c.
References forloop_body, inout_any_loop(), and one_trip_do_p.
Referenced by inout_statement().
Propagates in sets of ST (which is inherited) to compute the out sets.
st | is the statement that hold the loop |
lo | is the loop |
Definition at line 710 of file chains.c.
References inout_any_loop(), loop_body, loop_executed_at_least_once_p(), loop_executed_never_p(), and one_trip_do_p.
Referenced by inout_statement().
|
static |
Referenced by inout_any_loop(), inout_block(), inout_control(), inout_test(), and statement_dependence_graph().
|
static |
Propagates in sets of ST (which is inherited) to compute the out sets.
st | is the statement to compute |
Compute Def-Def and Def-Use conflicts from Def_in set
Compute Use-Def conflicts from Ref_in set
Compute "out" sets for the instruction : recursion
The second argument is not used
Definition at line 805 of file chains.c.
References add_conflicts(), current_defs, current_refs, dd_du(), DEF_OUT, ifdebug, inout_block(), inout_call(), inout_forloop(), inout_loop(), inout_test(), inout_unstructured(), inout_whileloop(), instruction_block, instruction_call, instruction_expression, instruction_forloop, instruction_loop, instruction_tag, instruction_test, instruction_unstructured, instruction_whileloop, is_instruction_block, is_instruction_call, is_instruction_expression, is_instruction_forloop, is_instruction_goto, is_instruction_loop, is_instruction_test, is_instruction_unstructured, is_instruction_whileloop, load_statement_effects(), local_print_statement_set(), pips_debug, pips_internal_error, REF_OUT, SET_FOREACH, statement_instruction, statement_number, statement_ordering, ud(), and vertex_statement().
Propagates in sets of ST (which is inherited) to compute the out sets.
st | is the statement that hold the test |
t | is the test |
Compute the out for the test
Definition at line 629 of file chains.c.
References current_defs, current_refs, inout_statement(), set_dup(), set_free(), set_union(), test_false, and test_true.
Referenced by inout_statement().
|
static |
Propagates in sets of ST (which is inherited) to compute the out sets.
st | is the statement that hold the unstructured |
u | is the unstructured |
Compute "in" sets
Compute the unstructured
Compute "out" sets
Definition at line 762 of file chains.c.
References CONTROL_MAP, control_statement, current_defs, current_refs, DEF_IN, DEF_OUT, empty, exit, gen_free_list(), inout_control(), MAKE_STATEMENT_SET, NIL, REF, ref, REF_IN, REF_OUT, set_assign(), set_free(), set_undefined_p, set_union(), unstructured_control, and unstructured_exit.
Referenced by inout_statement().
Propagates in sets of ST (which is inherited) to compute the out sets.
st | is the statement that hold the loop |
t | is the loop |
Definition at line 724 of file chains.c.
References inout_any_loop(), and whileloop_body.
Referenced by inout_statement().
The genref_xxx functions implement the computation of GEN and REF sets from Aho, Sethi and Ullman "Compilers" (p.
612). This is slightly more complex since we use a structured control graph, thus fixed point computations can be recursively required (the correctness of this is probable, although not proven, as far as I can tell). KILL_STATEMENT updates the KILL set of statement ST on entity LHS. Only effects that modify one reference (i.e., assignments) are killed (see above). Write effects on arrays (see IDXS) don't kill the definitions of the array. Equivalence with non-array entities is managed properly.
Kill the GEN set with a set of KILL effects
gen | the set to filter, modified by side effects |
killers | the "killer" effects |
A killer effect is exact and is a write (environment effects kills !!)
We only kill store effect
We avoid a self killing
Definition at line 244 of file chains.c.
References action_write_p, effect_action, effect_exact_p, effect_scalar_p(), first_exact_scalar_effect_certainly_includes_second_effect_p(), gen(), MAKE_STATEMENT_SET, set_add_element(), set_clear(), set_difference(), SET_FOREACH, set_free(), and store_effect_p().
Referenced by genref_block(), and inout_call().
else, flow thru!
FI: I wonder about iorgch; I would expect the same kind of stuff for the case expression, which may also hide a call to a user defined function, for instance via a for loop construct.
Definition at line 1276 of file chains.c.
References _FALLTHROUGH_, call_function, entity_initial, gen_append(), instruction_call, instruction_tag, iorgch, is_instruction_block, is_instruction_call, is_instruction_expression, is_instruction_forloop, is_instruction_goto, is_instruction_loop, is_instruction_test, is_instruction_unstructured, is_instruction_whileloop, is_value_code, load_proper_rw_effects_list(), load_statement_in_regions(), load_statement_out_regions(), NIL, pips_internal_error, statement_instruction, and value_tag.
Referenced by add_conflicts(), genref_one_statement(), init_one_statement(), and inout_statement().
Access functions for debug only.
displays on stderr, the MSG followed by the set of statement numbers associated to effects present in the set S.
msg | a string to be display at the beginning |
s | the set of effects to display |
Definition at line 144 of file chains.c.
References effects2statement, fprintf(), hash_get(), print_effect, SET_FOREACH, and statement_number.
Referenced by genref_statement(), inout_control(), and inout_statement().
MASK_EFFECTS masks the effects in S according to the locals L.
s | the set of effects |
l | the locals to mask |
Register which one we have to mask
Do the masking
We free because we are good programmers and we don't leak ;-)
Definition at line 331 of file chains.c.
References action_read_p, CONS, effect_action, effect_may_read_or_write_memory_paths_from_entity_p(), f(), FOREACH, gen_free_list(), NIL, set_del_element(), and SET_FOREACH.
Referenced by genref_any_loop(), and genref_block().
adds the conflict FIN->FOUT in the list CFS @description adds the conflict FIN->FOUT in the list CFS (if it's not already there, and apparently even if it's already there for performance reason...).
fin | is the incoming effect |
fout | is the sink effect |
cfs | is the list of conflict to update |
FI: This is a bottleneck for large modules with lots of callees and long effect lists. Let's assume that the pairs (fin, fout) are always unique because the effects are sets.
create the conflict
Add the conflict to the list
Definition at line 993 of file chains.c.
References cone_undefined, CONFLICT, CONS, effect_entity(), entity_name, fprintf(), ifdebug, and make_conflict().
Referenced by add_conflicts().
Phase to compute atomic chains based on array regions.
module_name | odule_name |
Definition at line 1449 of file chains.c.
References chains(), module_name(), and USE_REGIONS.
|
static |
Some forward declarations.
Definition at line 1379 of file chains.c.
References iorgch, reset_in_effects(), reset_out_effects(), and reset_proper_rw_effects().
Referenced by chains().
|
static |
Select the type of effects used to compute dependence chains.
Definition at line 1318 of file chains.c.
References db_get_memory_resource(), iorgch, module_name(), pips_internal_error, rgch, set_in_effects(), set_out_effects(), set_proper_rw_effects(), USE_IN_OUT_REGIONS, USE_PROPER_EFFECTS, and USE_REGIONS.
Referenced by chains().
Compute from a given statement, the dependency graph.
cproto-generated files
@description Statement s is assumed "controlized", i.e. GOTO have been replaced by unstructured.
FIXME FI: this function is bugged. As Pierre said, you have to start with an unstructured for the use-def chain computation to be correct.
Initialize some properties
Initialize global hashtables
Initialize the dg
Initialize data structures for all the statements
It recursively initializes the sets of gens, ins and outs for the statements that appear in st. Note that not only call statements are there, but also enclosing statements (e.g, blocks and loops).
Compute genref phase
Compute inout phase and create conflicts
Definition at line 1218 of file chains.c.
References current_defs, current_refs, dataflow_dependence_only_p, Def_in, Def_out, dg, effects2statement, Gen, gen_null(), gen_recurse, genref_statement(), get_bool_property(), hash_pointer, hash_table_free(), hash_table_make(), init_one_statement(), INIT_STATEMENT_SIZE, inout_statement(), keep_read_read_dependences_p, make_graph(), mask_effects_p, NIL, one_trip_do_p, Ref, Ref_in, Ref_out, set_free(), set_make(), set_pointer, statement_domain, TABLE_FREE, and Vertex_statement.
Referenced by chains().
UD detects Use/Def conflicts between effects FIN and FOUT.
Definition at line 1038 of file chains.c.
References action_read_p, action_write_p, effect_action, and keep_read_read_dependences_p.
Referenced by add_conflicts(), create_parameters_h(), and inout_statement().
Definition at line 159 of file chains.c.
References hash_get(), HASH_UNDEFINED_VALUE, pips_assert, and Vertex_statement.
Referenced by add_conflicts(), and inout_statement().
|
static |
current_defs is the set of DEF at the current point of the computation
Definition at line 100 of file chains.c.
Referenced by inout_any_loop(), inout_call(), inout_control(), inout_statement(), inout_test(), inout_unstructured(), and statement_dependence_graph().
|
static |
Definition at line 101 of file chains.c.
Referenced by inout_any_loop(), inout_call(), inout_control(), inout_statement(), inout_test(), inout_unstructured(), and statement_dependence_graph().
|
static |
Definition at line 133 of file chains.c.
Referenced by dd_du(), and statement_dependence_graph().
|
static |
Def_in maps each statement to the statements that are in-coming the statement It's only used for unstructured, current_defs is used for structured parts.
Definition at line 105 of file chains.c.
Referenced by init_one_statement(), and statement_dependence_graph().
|
static |
Def_out maps each statement to the statements that are out-coming the statement It's only used for unstructured, current_defs is used for structured parts.
Definition at line 110 of file chains.c.
Referenced by init_one_statement(), and statement_dependence_graph().
|
static |
dg is the dependency graph ; FIXME : should not be static global ?
Definition at line 124 of file chains.c.
Referenced by array_dfg(), bottom_level(), check_tiling_legality(), comEngine_distribute(), comEngine_distribute_code(), comEngine_feasability(), defs_elim_of_assign_call(), defs_elim_of_statement(), defs_elim_of_unstructured(), do_reduction_detection(), do_reduction_propagation(), do_redundant_load_store_elimination(), do_scalar_renaming(), forward_substitute(), freia_mppa_compile_calls(), fs_filter(), full_parallel_loop_nest_p(), get_vertex_of_statement(), if_conversion_compact(), if_conversion_compact_stats(), init_one_statement(), initialization(), instruction_to_wp65_code(), invariant_code_motion(), loop_nest_to_local_variables(), loop_nest_to_wp65_code(), module_to_wp65_modules(), mppa_call_helper(), mppa_dag_maybe_split_instrs_cmd(), mppa_dag_split(), parse_instrumented_file(), phrase_remove_dependences(), print_dependence_or_chains_graph(), print_dot_dependence_or_chains_graph(), print_filtered_dg_or_dvdg(), print_loopnest_dependence_cone(), reference_conflicting_p(), reference_conflicting_test_and_update(), sc_delimiter(), sc_get_port_id(), sc_kernel_specific_agent(), scalar_renaming(), search_parallel_loops(), sigmac_name_instances(), sigmac_params_decl(), simplify_dg(), statement_dependence_graph(), statements_to_successors(), t_level(), top_level(), wp65(), and xml_Chains().
|
static |
Mapping from effects to the associated statement.
Definition at line 89 of file chains.c.
Referenced by add_conflicts(), genref_one_statement(), init_one_statement(), local_print_statement_set(), and statement_dependence_graph().
|
static |
Gen maps each statement to the effects it generates.
Definition at line 92 of file chains.c.
Referenced by init_one_statement(), and statement_dependence_graph().
Definition at line 1274 of file chains.c.
Referenced by load_statement_effects(), reset_effects(), and set_effects().
|
static |
Definition at line 131 of file chains.c.
Referenced by statement_dependence_graph(), and ud().
|
static |
Definition at line 132 of file chains.c.
Referenced by genref_any_loop(), genref_block(), and statement_dependence_graph().
|
static |
Some properties.
Definition at line 130 of file chains.c.
Referenced by genref_forloop(), genref_loop(), genref_whileloop(), inout_any_loop(), inout_forloop(), inout_loop(), and statement_dependence_graph().
|
static |
Refs maps each statement to the effects it references.
Definition at line 96 of file chains.c.
Referenced by AllocateDadStruct(), GetRefTemp(), init_one_statement(), statement_dependence_graph(), TransRefTemp(), and update_indices_for_local_computation().
|
static |
Ref_in maps each statement to the effects that are in-coming the statement It's only used for unstructured, current_refs is used for structured parts.
Definition at line 115 of file chains.c.
Referenced by init_one_statement(), and statement_dependence_graph().
|
static |
Ref_out maps each statement to the effects that are out-coming the statement It's only used for unstructured, current_refs is used for structured parts.
Definition at line 120 of file chains.c.
Referenced by init_one_statement(), and statement_dependence_graph().
|
static |
Vertex_statement maps each statement to its vertex in the dependency graph.
Definition at line 127 of file chains.c.
Referenced by init_one_statement(), statement_dependence_graph(), and vertex_statement().