isl_transitive_closure.c File Reference

#include <isl_ctx_private.h>
#include <isl_map_private.h>
#include <isl/map.h>
#include <isl_seq.h>
#include <isl_space_private.h>
#include <isl_lp_private.h>
#include <isl/union_map.h>
#include <isl_mat_private.h>
#include <isl_vec_private.h>
#include <isl_options_private.h>
#include <isl_tarjan.h>
#include "isl_power_templ.c"

Go to the source code of this file.

Classes
struct	isl_tc_follows_data
struct	isl_union_power

Macros
#define	IMPURE   0
#define	PURE_PARAM   1
#define	PURE_VAR   2
#define	MIXED   3
#define	LEFT   2
#define	RIGHT   1
#define	TYPE   isl_map
#define	TYPE   isl_union_map

Functions
isl_bool	isl_map_is_transitively_closed (__isl_keep isl_map *map)
isl_bool	isl_union_map_is_transitively_closed (__isl_keep isl_union_map *umap)
static __isl_give isl_map *	set_path_length (__isl_take isl_map *map, int exactly, int length)
static isl_bool	check_power_exactness (__isl_take isl_map *map, __isl_take isl_map *app)
static isl_bool	check_exactness (__isl_take isl_map *map, __isl_take isl_map *app, int project)
static __isl_give isl_map *	path_along_steps (__isl_take isl_space *space, __isl_keep isl_mat *steps)
static isl_bool	parametric_constant_never_positive (__isl_keep isl_basic_set *bset, isl_int *c, int *div_purity)
static int	purity (__isl_keep isl_basic_set *bset, isl_int *c, int *div_purity, int eq)
static __isl_give int *	get_div_purity (__isl_keep isl_basic_set *bset)
static isl_bool	empty_path_is_identity (__isl_keep isl_basic_map *path, unsigned pos)
static __isl_give isl_basic_map *	add_delta_constraints (__isl_take isl_basic_map *path, __isl_keep isl_basic_set *delta, unsigned off, unsigned nparam, unsigned d, int *div_purity, int eq, int *impurity)
static __isl_give isl_map *	path_along_delta (__isl_take isl_space *space, __isl_take isl_basic_set *delta)
static __isl_give isl_map *	equate_parameter_to_length (__isl_take isl_space *space, unsigned param)
static isl_bool	is_acyclic (__isl_take isl_map *path)
static __isl_give isl_map *	construct_extended_path (__isl_take isl_space *space, __isl_keep isl_map *map, int *project)
static isl_bool	isl_set_overlaps (__isl_keep isl_set *set1, __isl_keep isl_set *set2)
static __isl_give isl_map *	construct_component (__isl_take isl_space *space, __isl_keep isl_map *map, isl_bool *exact, int project)
static __isl_give isl_map *	construct_projected_component (__isl_take isl_space *space, __isl_keep isl_map *map, isl_bool *exact, int project)
static __isl_give isl_map *	q_closure (__isl_take isl_space *space, __isl_take isl_set *dom, __isl_keep isl_basic_map *bmap, isl_bool *exact)
static isl_bool	has_spurious_elements (__isl_keep isl_map *qc, __isl_keep isl_set *dom, __isl_keep isl_set *ran)
static int	composability (__isl_keep isl_set *C, int i, isl_set **dom, isl_set **ran, int *left, int *right, __isl_keep isl_map *map)
static __isl_give isl_map *	anonymize (__isl_take isl_map *map)
static __isl_give isl_map *	compose (__isl_keep isl_map *map, int i, __isl_take isl_map *qc, int *left, int *right)
static __isl_give isl_map *	compute_incremental (__isl_take isl_space *space, __isl_keep isl_map *map, int i, __isl_take isl_map *qc, int *left, int *right, isl_bool *exact)
static isl_bool	incremental_on_entire_domain (__isl_keep isl_space *space, __isl_keep isl_map *map, isl_set **dom, isl_set **ran, int *left, int *right, __isl_give isl_map **res)
static __isl_give isl_map *	incremental_closure (__isl_take isl_space *space, __isl_keep isl_map *map, isl_bool *exact, int project)
static int	merge (isl_set **set, int *group, __isl_take isl_set *dom, int pos)
static __isl_give isl_map *	increment (__isl_take isl_space *space)
static isl_stat	add_length (__isl_keep isl_map *map, isl_map ***grid, int n)
static void	floyd_warshall_iterate (isl_map ***grid, int n, isl_bool *exact)
static __isl_give isl_map *	floyd_warshall_with_groups (__isl_take isl_space *space, __isl_keep isl_map *map, isl_bool *exact, int project, int *group, int n)
static int *	setup_groups (isl_ctx *ctx, __isl_keep isl_basic_map **list, int n, isl_set ***set, int *n_group)
static __isl_give isl_map *	floyd_warshall (__isl_take isl_space *space, __isl_keep isl_map *map, isl_bool *exact, int project)
static isl_bool	basic_map_follows (int i, int j, void *user)
static __isl_give isl_map *	construct_power_components (__isl_take isl_space *space, __isl_keep isl_map *map, isl_bool *exact, int project)
static __isl_give isl_map *	construct_power (__isl_keep isl_map *map, isl_bool *exact, int project)
static __isl_give isl_map *	map_power (__isl_take isl_map *map, isl_bool *exact, int project)
__isl_give isl_map *	isl_map_power (__isl_take isl_map *map, isl_bool *exact)
__isl_give isl_map *	isl_map_reaching_path_lengths (__isl_take isl_map *map, isl_bool *exact)
static __isl_give isl_map *	box_closure_on_domain (__isl_take isl_map *map, __isl_take isl_set *dom, __isl_take isl_set *ran, int with_id)
static __isl_give isl_map *	box_closure (__isl_take isl_map *map)
static __isl_give isl_map *	box_closure_with_identity (__isl_take isl_map *map, __isl_take isl_set *dom)
static isl_bool	check_exactness_omega (__isl_keep isl_map *map, __isl_keep isl_map *app)
static int	can_be_split_off (__isl_keep isl_map *map, int i, __isl_give isl_map **tc, __isl_give isl_map **qc)
static __isl_give isl_map *	box_closure_with_check (__isl_take isl_map *map, isl_bool *exact)
static __isl_give isl_map *	transitive_closure_omega (__isl_take isl_map *map, isl_bool *exact)
__isl_give isl_map *	isl_map_transitive_closure (__isl_take isl_map *map, isl_bool *exact)
static isl_stat	inc_count (__isl_take isl_map *map, void *user)
static isl_stat	collect_basic_map (__isl_take isl_map *map, void *user)
static __isl_give isl_union_map *	union_floyd_warshall_on_list (isl_ctx *ctx, __isl_keep isl_basic_map **list, int n, isl_bool *exact)
static __isl_give isl_union_map *	union_floyd_warshall (__isl_take isl_union_map *umap, isl_bool *exact)
static __isl_give isl_union_map *	union_components (__isl_take isl_union_map *umap, isl_bool *exact)
__isl_give isl_union_map *	isl_union_map_transitive_closure (__isl_take isl_union_map *umap, isl_bool *exact)
static isl_stat	power (__isl_take isl_map *map, void *user)
static __isl_give isl_union_map *	deltas_map (__isl_take isl_space *space)
__isl_give isl_union_map *	isl_union_map_power (__isl_take isl_union_map *umap, isl_bool *exact)

Macro Definition Documentation

IMPURE

#define IMPURE   0

Definition at line 289 of file isl_transitive_closure.c.

LEFT

#define LEFT   2

Definition at line 1009 of file isl_transitive_closure.c.

MIXED

#define MIXED   3

Definition at line 292 of file isl_transitive_closure.c.

PURE_PARAM

#define PURE_PARAM   1

Definition at line 290 of file isl_transitive_closure.c.

PURE_VAR

#define PURE_VAR   2

Definition at line 291 of file isl_transitive_closure.c.

RIGHT

#define RIGHT   1

Definition at line 1010 of file isl_transitive_closure.c.

TYPE [1/2]

#define TYPE   isl_map

Definition at line 2946 of file isl_transitive_closure.c.

TYPE [2/2]

#define TYPE   isl_union_map

Definition at line 2946 of file isl_transitive_closure.c.

Function Documentation

add_delta_constraints()

static __isl_give isl_basic_map * add_delta_constraints ( __isl_take isl_basic_map *  path, __isl_keep isl_basic_set *  delta, unsigned  off, unsigned  nparam, unsigned  d, int *  div_purity, int  eq, int *  impurity  )

static

Definition at line 461 of file isl_transitive_closure.c.

References isl_basic_map::eq, IMPURE, isl_basic_map_alloc_equality(), isl_basic_map_alloc_inequality(), isl_basic_map_dim(), isl_basic_map_free(), isl_basic_set_dim(), isl_dim_all, isl_dim_div, isl_int_set, isl_seq_clr(), isl_seq_cpy(), MIXED, n, isl_basic_map::n_div, p, PURE_PARAM, PURE_VAR, purity(), and total().

Referenced by path_along_delta().

add_length()

static isl_stat add_length ( __isl_keep isl_map *  map, isl_map ***  grid, int  n  )

static

Definition at line 1514 of file isl_transitive_closure.c.

References increment(), isl_map_copy(), isl_map_free(), isl_map_get_space(), isl_map_product(), isl_space_params(), isl_stat_error, isl_stat_ok, map, and n.

Referenced by floyd_warshall_with_groups().

anonymize()

static __isl_give isl_map * anonymize ( __isl_take isl_map *  map )

static

Definition at line 1104 of file isl_transitive_closure.c.

References isl_dim_in, isl_dim_out, isl_map_reset(), and map.

Referenced by compose(), and construct_power_components().

basic_map_follows()

static isl_bool basic_map_follows ( int  i, int  j, void *  user  )

static

Definition at line 1796 of file isl_transitive_closure.c.

References isl_tc_follows_data::check_closed, isl_basic_map_applies_range(), isl_basic_map_apply_range(), isl_basic_map_copy(), isl_basic_map_is_transformation(), isl_bool_error, isl_bool_false, isl_bool_not(), isl_bool_true, isl_map_free(), isl_map_from_basic_map(), isl_map_is_empty(), isl_map_is_subset(), isl_tc_follows_data::list, subset, and user.

Referenced by construct_power_components(), and union_components().

box_closure()

static __isl_give isl_map * box_closure ( __isl_take isl_map *  map )

static

Definition at line 2302 of file isl_transitive_closure.c.

References box_closure_on_domain(), domain, isl_map_copy(), isl_map_domain(), isl_map_range(), isl_set_coalesce(), map, and range.

Referenced by box_closure_with_check(), and can_be_split_off().

box_closure_on_domain()

static __isl_give isl_map * box_closure_on_domain ( __isl_take isl_map *  map, __isl_take isl_set *  dom, __isl_take isl_set *  ran, int  with_id  )

static

Definition at line 2164 of file isl_transitive_closure.c.

References aff, isl_basic_map::div, isl_basic_map::eq, isl_basic_map::ineq, isl_basic_map_alloc_div(), isl_basic_map_alloc_equality(), isl_basic_map_alloc_inequality(), isl_basic_map_alloc_space(), isl_basic_map_finalize(), isl_basic_map_free(), isl_basic_set_eq_is_stride(), isl_basic_set_free(), isl_dim_all, isl_dim_in, isl_dim_param, isl_int_clear, isl_int_init, isl_int_neg, isl_int_set, isl_int_set_si, isl_lp_error, isl_lp_ok, isl_map_copy(), isl_map_deltas(), isl_map_free(), isl_map_from_basic_map(), isl_map_from_domain_and_range(), isl_map_get_space(), isl_map_intersect(), isl_seq_clr(), isl_seq_cpy(), isl_seq_neg(), isl_set_affine_hull(), isl_set_copy(), isl_set_free(), isl_set_solve_lp(), isl_space_dim(), isl_vec_alloc(), isl_vec_free(), map, isl_basic_map::n_div, obj, res, and total().

Referenced by box_closure(), and box_closure_with_identity().

box_closure_with_check()

static __isl_give isl_map * box_closure_with_check ( __isl_take isl_map *  map, isl_bool *  exact  )

static

Definition at line 2462 of file isl_transitive_closure.c.

References box_closure(), check_exactness_omega(), isl_map_copy(), isl_map_free(), and map.

Referenced by transitive_closure_omega().

box_closure_with_identity()

static __isl_give isl_map * box_closure_with_identity ( __isl_take isl_map *  map, __isl_take isl_set *  dom  )

static

Definition at line 2328 of file isl_transitive_closure.c.

References box_closure_on_domain(), isl_set_copy(), and map.

Referenced by can_be_split_off().

can_be_split_off()

static int can_be_split_off ( __isl_keep isl_map *  map, int  i, __isl_give isl_map **  tc, __isl_give isl_map **  qc  )

static

Definition at line 2396 of file isl_transitive_closure.c.

References box_closure(), box_closure_with_identity(), C, id, isl_basic_map_copy(), isl_map_apply_range(), isl_map_copy(), isl_map_domain(), isl_map_free(), isl_map_from_basic_map(), isl_map_is_equal(), isl_map_range(), isl_map_subtract(), isl_set_from_basic_set(), isl_set_simple_hull(), isl_set_union(), map, and test.

Referenced by transitive_closure_omega().

check_exactness()

static isl_bool check_exactness ( __isl_take isl_map *  map, __isl_take isl_map *  app, int  project  )

static

Definition at line 173 of file isl_transitive_closure.c.

References check_power_exactness(), isl_dim_in, isl_dim_out, isl_map_apply_range(), isl_map_copy(), isl_map_dim(), isl_map_free(), isl_map_get_space(), isl_map_is_subset(), isl_map_project_out(), isl_map_reset_space(), isl_map_union(), map, set_path_length(), and test.

Referenced by construct_component(), and q_closure().

check_exactness_omega()

static isl_bool check_exactness_omega ( __isl_keep isl_map *  map, __isl_keep isl_map *  app  )

static

Definition at line 2340 of file isl_transitive_closure.c.

References isl_dim_set, isl_map_apply_range(), isl_map_copy(), isl_map_deltas(), isl_map_free(), isl_map_is_subset(), isl_map_union(), isl_set_dim(), isl_set_fix_si(), isl_set_free(), isl_set_is_empty(), map, and test.

Referenced by box_closure_with_check(), and transitive_closure_omega().

check_power_exactness()

static isl_bool check_power_exactness ( __isl_take isl_map *  map, __isl_take isl_map *  app  )

static

Definition at line 118 of file isl_transitive_closure.c.

References isl_dim_in, isl_dim_out, isl_map_add_dims(), isl_map_apply_range(), isl_map_copy(), isl_map_free(), isl_map_is_subset(), map, and set_path_length().

Referenced by check_exactness().

collect_basic_map()

static isl_stat collect_basic_map ( __isl_take isl_map *  map, void *  user  )

static

Definition at line 2601 of file isl_transitive_closure.c.

References isl_basic_map_copy(), isl_map_free(), isl_stat_error, isl_stat_ok, map, and user.

Referenced by union_components(), and union_floyd_warshall().

composability()

static int composability ( __isl_keep isl_set *  C, int  i, isl_set **  dom, isl_set **  ran, int *  left, int *  right, __isl_keep isl_map *  map  )

static

Definition at line 1041 of file isl_transitive_closure.c.

References C, isl_basic_map_copy(), isl_basic_map_domain(), isl_basic_map_range(), isl_set_from_basic_set(), isl_set_is_subset(), isl_set_overlaps(), LEFT, map, RIGHT, and subset.

Referenced by incremental_closure().

compose()

static __isl_give isl_map * compose ( __isl_keep isl_map *  map, int  i, __isl_take isl_map *  qc, int *  left, int *  right  )

static

Definition at line 1115 of file isl_transitive_closure.c.

References anonymize(), isl_basic_map_copy(), isl_map_apply_range(), isl_map_coalesce(), isl_map_compute_divs(), isl_map_copy(), isl_map_empty(), isl_map_free(), isl_map_from_basic_map(), isl_map_get_space(), isl_map_union(), and map.

Referenced by incremental_closure(), and incremental_on_entire_domain().

compute_incremental()

static __isl_give isl_map * compute_incremental ( __isl_take isl_space *  space, __isl_keep isl_map *  map, int  i, __isl_take isl_map *  qc, int *  left, int *  right, isl_bool *  exact  )

static

Definition at line 1160 of file isl_transitive_closure.c.

References construct_projected_component(), isl_assert, isl_basic_map_copy(), isl_map_apply_range(), isl_map_copy(), isl_map_free(), isl_map_from_basic_map(), isl_map_get_space(), isl_map_identity(), isl_map_transitive_closure(), isl_map_union(), isl_map_universe(), isl_space_copy(), isl_space_free(), and map.

Referenced by incremental_closure(), and incremental_on_entire_domain().

construct_component()

static __isl_give isl_map * construct_component ( __isl_take isl_space *  space, __isl_keep isl_map *  map, isl_bool *  exact, int  project  )

static

Definition at line 868 of file isl_transitive_closure.c.

References check_exactness(), construct_extended_path(), domain, isl_bool_true, isl_dim_in, isl_dim_out, isl_map_add_dims(), isl_map_copy(), isl_map_domain(), isl_map_free(), isl_map_from_domain_and_range(), isl_map_intersect(), isl_map_range(), isl_set_coalesce(), isl_set_free(), isl_set_overlaps(), isl_space_copy(), isl_space_free(), map, range, and set_path_length().

Referenced by construct_projected_component().

construct_extended_path()

static __isl_give isl_map * construct_extended_path ( __isl_take isl_space *  space, __isl_keep isl_map *  map, int *  project  )

static

Definition at line 773 of file isl_transitive_closure.c.

References is_acyclic(), isl_basic_map_copy(), isl_basic_map_deltas(), isl_basic_set_free(), isl_basic_set_plain_dim_is_fixed(), isl_dim_in, isl_map_apply_range(), isl_map_coalesce(), isl_map_copy(), isl_map_dim(), isl_map_free(), isl_map_identity(), isl_mat_alloc(), isl_mat_free(), isl_space_copy(), isl_space_free(), map, n, isl_mat::n_row, path_along_delta(), path_along_steps(), and isl_mat::row.

Referenced by construct_component(), and q_closure().

construct_power()

static __isl_give isl_map * construct_power ( __isl_keep isl_map *  map, isl_bool *  exact, int  project  )

static

Definition at line 1988 of file isl_transitive_closure.c.

References construct_power_components(), isl_dim_in, isl_dim_out, isl_map_get_space(), isl_space_add_dims(), isl_space_copy(), isl_space_free(), and map.

Referenced by map_power().

construct_power_components()

static __isl_give isl_map * construct_power_components ( __isl_take isl_space *  space, __isl_keep isl_map *  map, isl_bool *  exact, int  project  )

static

Definition at line 1879 of file isl_transitive_closure.c.

References anonymize(), basic_map_follows(), isl_tc_follows_data::check_closed, floyd_warshall(), isl_basic_map_copy(), isl_map_add_basic_map(), isl_map_alloc_space(), isl_map_apply_range(), isl_map_copy(), isl_map_empty(), isl_map_free(), isl_map_get_space(), isl_map_is_transitively_closed(), isl_map_union(), isl_space_copy(), isl_space_free(), isl_tarjan_graph_free(), isl_tarjan_graph_init(), isl_tc_follows_data::list, map, n, and isl_tarjan_graph::order.

Referenced by construct_power().

construct_projected_component()

static __isl_give isl_map * construct_projected_component ( __isl_take isl_space *  space, __isl_keep isl_map *  map, isl_bool *  exact, int  project  )

static

Definition at line 922 of file isl_transitive_closure.c.

References construct_component(), isl_dim_in, isl_dim_out, isl_map_project_out(), isl_space_dim(), and map.

Referenced by compute_incremental(), and incremental_closure().

deltas_map()

static __isl_give isl_union_map * deltas_map ( __isl_take isl_space *  space )

static

Definition at line 2897 of file isl_transitive_closure.c.

References isl_basic_map_deltas_map(), isl_basic_map_universe(), isl_dim_in, isl_dim_out, isl_map_from_basic_map(), isl_space_add_dims(), and isl_union_map_from_map().

Referenced by isl_union_map_power().

empty_path_is_identity()

static isl_bool empty_path_is_identity ( __isl_keep isl_basic_map *  path, unsigned  pos  )

static

Definition at line 439 of file isl_transitive_closure.c.

References isl_basic_map_copy(), isl_basic_map_fix_si(), isl_basic_map_free(), isl_basic_map_get_space(), isl_basic_map_identity(), isl_basic_map_is_equal(), isl_dim_div, pos(), and test.

Referenced by path_along_delta().

equate_parameter_to_length()

static __isl_give isl_map * equate_parameter_to_length ( __isl_take isl_space *  space, unsigned  param  )

static

Definition at line 678 of file isl_transitive_closure.c.

References isl_basic_map::eq, isl_basic_map::ineq, isl_basic_map_alloc_equality(), isl_basic_map_alloc_inequality(), isl_basic_map_alloc_space(), isl_basic_map_finalize(), isl_basic_map_free(), isl_dim_all, isl_dim_in, isl_dim_param, isl_int_set_si, isl_map_from_basic_map(), isl_seq_clr(), isl_space_dim(), isl_space_free(), and total().

Referenced by isl_map_power(), and isl_map_reaching_path_lengths().

floyd_warshall()

static __isl_give isl_map * floyd_warshall ( __isl_take isl_space *  space, __isl_keep isl_map *  map, isl_bool *  exact, int  project  )

static

Definition at line 1738 of file isl_transitive_closure.c.

References floyd_warshall_with_groups(), incremental_closure(), isl_set_free(), isl_space_free(), map, n, set, and setup_groups().

Referenced by construct_power_components().

floyd_warshall_iterate()

static void floyd_warshall_iterate ( isl_map ***  grid, int  n, isl_bool *  exact  )

static

Definition at line 1547 of file isl_transitive_closure.c.

References isl_bool_false, isl_bool_true, isl_map_apply_range(), isl_map_coalesce(), isl_map_copy(), isl_map_transitive_closure(), isl_map_union(), n, and p.

Referenced by floyd_warshall_with_groups(), and union_floyd_warshall_on_list().

floyd_warshall_with_groups()

static __isl_give isl_map * floyd_warshall_with_groups ( __isl_take isl_space *  space, __isl_keep isl_map *  map, isl_bool *  exact, int  project, int *  group, int  n  )

static

Definition at line 1598 of file isl_transitive_closure.c.

References add_length(), floyd_warshall_iterate(), incremental_closure(), isl_basic_map_copy(), isl_calloc_array, isl_map_empty(), isl_map_free(), isl_map_from_basic_map(), isl_map_get_space(), isl_map_union(), isl_space_free(), map, and n.

Referenced by floyd_warshall().

get_div_purity()

static __isl_give int * get_div_purity ( __isl_keep isl_basic_set *  bset )

static

Definition at line 392 of file isl_transitive_closure.c.

References IMPURE, isl_alloc_array, isl_basic_set_dim(), isl_dim_div, isl_dim_param, isl_dim_set, isl_int_is_zero, isl_seq_first_non_zero(), isl_basic_map::n_div, p, PURE_PARAM, and PURE_VAR.

Referenced by path_along_delta().

has_spurious_elements()

static isl_bool has_spurious_elements ( __isl_keep isl_map *  qc, __isl_keep isl_set *  dom, __isl_keep isl_set *  ran  )

static

Definition at line 973 of file isl_transitive_closure.c.

References isl_bool_error, isl_bool_not(), isl_bool_true, isl_dim_in, isl_dim_out, isl_map_copy(), isl_map_dim(), isl_map_domain(), isl_map_free(), isl_map_project_out(), isl_map_range(), isl_set_free(), isl_set_is_subset(), set_path_length(), and subset.

Referenced by incremental_closure(), and incremental_on_entire_domain().

inc_count()

static isl_stat inc_count ( __isl_take isl_map *  map, void *  user  )

static

Definition at line 2590 of file isl_transitive_closure.c.

References isl_map_free(), isl_stat_ok, map, n, and user.

Referenced by test_schedule_tree(), test_schedule_tree_generic(), union_components(), and union_floyd_warshall().

increment()

static __isl_give isl_map * increment ( __isl_take isl_space *  space )

static

Definition at line 1487 of file isl_transitive_closure.c.

References isl_basic_map::eq, isl_basic_map_alloc_equality(), isl_basic_map_alloc_space(), isl_basic_map_dim(), isl_basic_map_free(), isl_basic_map_offset(), isl_dim_all, isl_dim_in, isl_dim_out, isl_dim_set, isl_int_set_si, isl_map_from_basic_map(), isl_seq_clr(), isl_space_add_dims(), isl_space_map_from_set(), isl_space_set_from_params(), and total().

Referenced by add_length(), and isl_union_map_power().

incremental_closure()

static __isl_give isl_map * incremental_closure ( __isl_take isl_space *  space, __isl_keep isl_map *  map, isl_bool *  exact, int  project  )

static

Definition at line 1307 of file isl_transitive_closure.c.

References C, composability(), compose(), compute_incremental(), construct_projected_component(), has_spurious_elements(), incremental_on_entire_domain(), isl_basic_map_copy(), isl_basic_map_domain(), isl_basic_map_range(), isl_calloc_array, isl_dim_in, isl_dim_out, isl_map_compute_divs(), isl_map_dim(), isl_map_free(), isl_map_project_out(), isl_set_copy(), isl_set_free(), isl_set_from_basic_set(), isl_set_simple_hull(), isl_set_union(), isl_space_copy(), isl_space_free(), LEFT, map, isl_map::n, q_closure(), res, and RIGHT.

Referenced by floyd_warshall(), and floyd_warshall_with_groups().

incremental_on_entire_domain()

static isl_bool incremental_on_entire_domain ( __isl_keep isl_space *  space, __isl_keep isl_map *  map, isl_set **  dom, isl_set **  ran, int *  left, int *  right, __isl_give isl_map **  res  )

static

Definition at line 1220 of file isl_transitive_closure.c.

References C, compose(), compute_incremental(), has_spurious_elements(), isl_basic_map_copy(), isl_basic_map_domain(), isl_basic_map_range(), isl_bool_error, isl_bool_false, isl_bool_ok(), isl_dim_in, isl_dim_out, isl_map_compute_divs(), isl_map_copy(), isl_map_dim(), isl_map_domain(), isl_map_free(), isl_map_project_out(), isl_map_range(), isl_set_copy(), isl_set_free(), isl_set_from_basic_set(), isl_set_simple_hull(), isl_set_union(), isl_space_copy(), map, isl_map::n, q_closure(), and res.

Referenced by incremental_closure().

is_acyclic()

static isl_bool is_acyclic ( __isl_take isl_map *  path )

static

Definition at line 724 of file isl_transitive_closure.c.

References isl_basic_map::dim, isl_dim_set, isl_map_deltas(), isl_set_dim(), isl_set_fix_si(), isl_set_free(), isl_set_is_empty(), and isl_set_lower_bound_si().

Referenced by construct_extended_path().

isl_map_is_transitively_closed()

isl_bool isl_map_is_transitively_closed

(

__isl_keep isl_map *

map

)

Definition at line 23 of file isl_transitive_closure.c.

References isl_map_apply_range(), isl_map_copy(), isl_map_free(), isl_map_is_subset(), map, and map2.

Referenced by construct_power_components(), and isl_map_transitive_closure().

isl_map_power()

__isl_give isl_map * isl_map_power	(	__isl_take isl_map *	map,
		isl_bool *	exact
	)

Definition at line 2044 of file isl_transitive_closure.c.

References equate_parameter_to_length(), isl_dim_in, isl_dim_out, isl_dim_param, isl_map_add_dims(), isl_map_coalesce(), isl_map_compute_divs(), isl_map_dim(), isl_map_free(), isl_map_from_range(), isl_map_get_space(), isl_map_intersect(), isl_map_move_dims(), isl_map_plain_is_empty(), isl_map_project_out(), isl_map_reset_space(), isl_map_set_dim_name(), isl_map_wrap(), isl_space_add_dims(), isl_space_from_range(), isl_space_set_dim_name(), isl_space_wrap(), map, and map_power().

Referenced by power(), and test_closure().

isl_map_reaching_path_lengths()

__isl_give isl_map * isl_map_reaching_path_lengths	(	__isl_take isl_map *	map,
		isl_bool *	exact
	)

Definition at line 2097 of file isl_transitive_closure.c.

References equate_parameter_to_length(), isl_bool_true, isl_dim_in, isl_dim_out, isl_dim_param, isl_map_add_dims(), isl_map_coalesce(), isl_map_compute_divs(), isl_map_dim(), isl_map_free(), isl_map_get_space(), isl_map_intersect(), isl_map_move_dims(), isl_map_plain_is_empty(), isl_map_project_out(), isl_map_reverse(), map, and map_power().

isl_map_transitive_closure()

__isl_give isl_map * isl_map_transitive_closure	(	__isl_take isl_map *	map,
		isl_bool *	exact
	)

Definition at line 2557 of file isl_transitive_closure.c.

References isl_bool_true, ISL_CLOSURE_BOX, isl_map_coalesce(), isl_map_compute_divs(), isl_map_free(), isl_map_get_space(), isl_map_is_transitively_closed(), isl_map_reset_space(), map, map_power(), and transitive_closure_omega().

Referenced by compute_incremental(), floyd_warshall_iterate(), main(), and test_closure().

isl_set_overlaps()

static isl_bool isl_set_overlaps ( __isl_keep isl_set *  set1, __isl_keep isl_set *  set2  )

static

Definition at line 843 of file isl_transitive_closure.c.

References isl_bool_not(), isl_set_is_disjoint(), set1, and set2.

Referenced by composability(), construct_component(), and merge().

isl_union_map_is_transitively_closed()

isl_bool isl_union_map_is_transitively_closed

(

__isl_keep isl_union_map *

umap

)

Definition at line 35 of file isl_transitive_closure.c.

References isl_union_map_apply_range(), isl_union_map_copy(), isl_union_map_free(), and isl_union_map_is_subset().

Referenced by isl_union_map_transitive_closure(), and union_components().

isl_union_map_power()

__isl_give isl_union_map * isl_union_map_power	(	__isl_take isl_union_map *	umap,
		isl_bool *	exact
	)

Definition at line 2913 of file isl_transitive_closure.c.

References deltas_map(), isl_union_power::exact, increment(), isl_union_map_apply_domain(), isl_union_map_foreach_map(), isl_union_map_free(), isl_union_map_from_map(), isl_union_map_get_space(), isl_union_map_n_map(), isl_union_map_product(), isl_union_map_transitive_closure(), isl_union_map_zip(), n, isl_union_power::pow, and power().

isl_union_map_transitive_closure()

__isl_give isl_union_map * isl_union_map_transitive_closure	(	__isl_take isl_union_map *	umap,
		isl_bool *	exact
	)

Definition at line 2855 of file isl_transitive_closure.c.

References isl_bool_true, isl_union_map_coalesce(), isl_union_map_compute_divs(), isl_union_map_free(), isl_union_map_is_transitively_closed(), and union_components().

Referenced by polly::Dependences::addPrivatizationDependences(), and isl_union_map_power().

map_power()

static __isl_give isl_map * map_power ( __isl_take isl_map *  map, isl_bool *  exact, int  project  )

static

Definition at line 2018 of file isl_transitive_closure.c.

References construct_power(), isl_bool_true, isl_map_check_transformation(), isl_map_free(), and map.

Referenced by isl_map_power(), isl_map_reaching_path_lengths(), and isl_map_transitive_closure().

merge()

static int merge ( isl_set **  set, int *  group, __isl_take isl_set *  dom, int  pos  )

static

Definition at line 1451 of file isl_transitive_closure.c.

References isl_set_copy(), isl_set_free(), isl_set_overlaps(), isl_set_union(), pos(), and set.

Referenced by setup_groups().

parametric_constant_never_positive()

static isl_bool parametric_constant_never_positive ( __isl_keep isl_basic_set *  bset, isl_int *  c, int *  div_purity  )

static

Definition at line 297 of file isl_transitive_closure.c.

References isl_basic_set_alloc_inequality(), isl_basic_set_copy(), isl_basic_set_cow(), isl_basic_set_dim(), isl_basic_set_extend_constraints(), isl_basic_set_free(), isl_basic_set_is_empty(), isl_bool_error, isl_dim_all, isl_dim_div, isl_dim_param, isl_dim_set, isl_int_set, isl_int_sub_ui, isl_seq_clr(), isl_seq_cpy(), isl_basic_map::n_div, PURE_PARAM, and total().

Referenced by purity().

path_along_delta()

static __isl_give isl_map * path_along_delta ( __isl_take isl_space *  space, __isl_take isl_basic_set *  delta  )

static

Definition at line 575 of file isl_transitive_closure.c.

References add_delta_constraints(), isl_basic_map::div, empty_path_is_identity(), isl_basic_map::eq, get_div_purity(), isl_basic_map::ineq, isl_basic_map_alloc_div(), isl_basic_map_alloc_equality(), isl_basic_map_alloc_inequality(), isl_basic_map_alloc_space(), isl_basic_map_dim(), isl_basic_map_extend_constraints(), isl_basic_map_finalize(), isl_basic_map_free(), isl_basic_map_gauss(), isl_basic_map_identity(), isl_basic_map_union(), isl_basic_set_add_dims(), isl_basic_set_dim(), isl_basic_set_free(), isl_basic_set_get_space(), isl_basic_set_project_out(), isl_basic_set_reset_space(), isl_dim_all, isl_dim_div, isl_dim_param, isl_dim_set, isl_int_set_si, isl_map_from_basic_map(), isl_seq_clr(), isl_space_copy(), isl_space_free(), isl_basic_map::n_div, isl_basic_map::n_eq, and total().

Referenced by construct_extended_path().

path_along_steps()

static __isl_give isl_map * path_along_steps ( __isl_take isl_space *  space, __isl_keep isl_mat *  steps  )

static

Definition at line 224 of file isl_transitive_closure.c.

References isl_basic_map::div, isl_basic_map::eq, isl_basic_map::ineq, isl_assert, isl_basic_map_alloc_div(), isl_basic_map_alloc_equality(), isl_basic_map_alloc_inequality(), isl_basic_map_alloc_space(), isl_basic_map_dim(), isl_basic_map_finalize(), isl_basic_map_free(), isl_basic_map_simplify(), isl_dim_all, isl_dim_in, isl_dim_param, isl_int_set, isl_int_set_si, isl_map_from_basic_map(), isl_seq_clr(), isl_space_copy(), isl_space_dim(), isl_space_free(), n, and total().

Referenced by construct_extended_path().

power()

static isl_stat power ( __isl_take isl_map *  map, void *  user  )

static

Definition at line 2885 of file isl_transitive_closure.c.

References isl_union_power::exact, isl_map_power(), isl_stat_error, isl_union_map_from_map(), map, isl_union_power::pow, and user.

Referenced by isl_poly_pow(), isl_poly_var_pow(), isl_pw_qpolynomial_pow(), isl_qpolynomial_pow(), isl_qpolynomial_var_pow_on_domain(), isl_union_map_power(), and test_qexpt().

purity()

static int purity ( __isl_keep isl_basic_set *  bset, isl_int *  c, int *  div_purity, int  eq  )

static

Definition at line 346 of file isl_transitive_closure.c.

References isl_basic_map::eq, IMPURE, isl_basic_set_dim(), isl_dim_div, isl_dim_param, isl_dim_set, isl_int_is_zero, isl_seq_first_non_zero(), isl_seq_neg(), MIXED, isl_basic_map::n_div, p, parametric_constant_never_positive(), PURE_PARAM, and PURE_VAR.

Referenced by add_delta_constraints().

q_closure()

static __isl_give isl_map * q_closure ( __isl_take isl_space *  space, __isl_take isl_set *  dom, __isl_keep isl_basic_map *  bmap, isl_bool *  exact  )

static

Definition at line 946 of file isl_transitive_closure.c.

References check_exactness(), construct_extended_path(), isl_basic_map_copy(), isl_dim_set, isl_map_copy(), isl_map_free(), isl_map_from_basic_map(), isl_map_from_domain_and_range(), isl_map_intersect(), isl_set_add_dims(), isl_set_copy(), and map.

Referenced by incremental_closure(), and incremental_on_entire_domain().

set_path_length()

static __isl_give isl_map * set_path_length ( __isl_take isl_map *  map, int  exactly, int  length  )

static

Definition at line 54 of file isl_transitive_closure.c.

References isl_basic_map::eq, isl_basic_map::ineq, isl_basic_map_alloc_equality(), isl_basic_map_alloc_inequality(), isl_basic_map_alloc_space(), isl_basic_map_finalize(), isl_basic_map_free(), isl_dim_all, isl_dim_in, isl_dim_param, isl_int_set_si, isl_map_free(), isl_map_from_basic_map(), isl_map_get_space(), isl_map_intersect(), isl_seq_clr(), isl_space_dim(), isl_space_free(), map, and total().

Referenced by check_exactness(), check_power_exactness(), construct_component(), and has_spurious_elements().

setup_groups()

static int * setup_groups ( isl_ctx *  ctx, __isl_keep isl_basic_map **  list, int  n, isl_set ***  set, int *  n_group  )

static

Definition at line 1680 of file isl_transitive_closure.c.

References isl_map::ctx, isl_alloc_array, isl_basic_map_copy(), isl_basic_map_domain(), isl_basic_map_range(), isl_calloc_array, isl_set_free(), isl_set_from_basic_set(), merge(), n, and set.

Referenced by floyd_warshall(), and union_floyd_warshall_on_list().

transitive_closure_omega()

static __isl_give isl_map * transitive_closure_omega ( __isl_take isl_map *  map, isl_bool *  exact  )

static

Definition at line 2499 of file isl_transitive_closure.c.

References box_closure_with_check(), can_be_split_off(), check_exactness_omega(), isl_basic_map_copy(), isl_bool_true, isl_map_add_basic_map(), isl_map_alloc_space(), isl_map_apply_range(), isl_map_copy(), isl_map_free(), isl_map_get_space(), isl_map_union(), map, and transitive_closure_omega().

Referenced by isl_map_transitive_closure(), and transitive_closure_omega().

union_components()

static __isl_give isl_union_map * union_components ( __isl_take isl_union_map *  umap, isl_bool *  exact  )

static

Definition at line 2755 of file isl_transitive_closure.c.

References basic_map_follows(), isl_tc_follows_data::check_closed, collect_basic_map(), isl_map::ctx, inc_count(), isl_basic_map_copy(), isl_basic_map_free(), isl_calloc_array, isl_map_from_basic_map(), isl_tarjan_graph_free(), isl_tarjan_graph_init(), isl_union_map_add_map(), isl_union_map_apply_range(), isl_union_map_copy(), isl_union_map_empty(), isl_union_map_foreach_map(), isl_union_map_free(), isl_union_map_get_ctx(), isl_union_map_get_space(), isl_union_map_is_transitively_closed(), isl_union_map_union(), isl_tc_follows_data::list, n, isl_tarjan_graph::order, and union_floyd_warshall().

Referenced by isl_union_map_transitive_closure().

union_floyd_warshall()

static __isl_give isl_union_map * union_floyd_warshall ( __isl_take isl_union_map *  umap, isl_bool *  exact  )

static

Definition at line 2708 of file isl_transitive_closure.c.

References collect_basic_map(), isl_map::ctx, inc_count(), isl_basic_map_free(), isl_calloc_array, isl_union_map_foreach_map(), isl_union_map_free(), isl_union_map_get_ctx(), n, res, and union_floyd_warshall_on_list().

Referenced by union_components().

union_floyd_warshall_on_list()

static __isl_give isl_union_map * union_floyd_warshall_on_list ( isl_ctx *  ctx, __isl_keep isl_basic_map **  list, int  n, isl_bool *  exact  )

static

Definition at line 2628 of file isl_transitive_closure.c.

References isl_map::ctx, floyd_warshall_iterate(), isl_basic_map_copy(), isl_calloc_array, isl_map_empty(), isl_map_free(), isl_map_from_basic_map(), isl_map_get_space(), isl_map_union(), isl_set_free(), isl_set_get_space(), isl_space_join(), isl_space_reverse(), isl_union_map_add_map(), isl_union_map_empty(), n, set, and setup_groups().

Referenced by union_floyd_warshall().