1 /* Structure of polyhedra.
2 Copyright (C) 2005 Free Software Foundation, Inc.
3 Contributed by Sebastian Pop <sebastian.pop@cri.ensmp.fr>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to the Free
19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
22 #ifndef GCC_POLYHEDRON_H
23 #define GCC_POLYHEDRON_H
28 /* A constraint system is composed of a system of linear equalities
29 and inequalities. Example: the following constraints system
34 is encoded by the matrix:
43 /* NB_CONSTRAINTS = NB_EQS + nb_ineqs. */
44 int dimension
, nb_eqs
, nb_constraints
;
46 /* CONSTRAINTS is NB_CONSTRAINTS lines by DIMENSION + 2 columns. */
47 lambda_matrix constraints
;
51 #define CSYS_DIMENSION(C) ((C)->dimension)
52 #define CSYS_NB_EQS(C) ((C)->nb_eqs)
53 #define CSYS_NB_CONSTRAINTS(C) ((C)->nb_constraints)
56 #define CSYS_M(C) ((C)->constraints)
58 #define CSYS_ELT(C, I, J) (CSYS_M (C)[I][J])
60 #define CSYS_CST(C, I) (CSYS_ELT (C, I, CSYS_DIMENSION (C) + 1))
62 #define CSYS_VECTOR(C, I) (CSYS_M (C)[I] + 1)
63 /* An element of the vector. */
64 #define CSYS_VEC(C, I, J) (CSYS_VECTOR (C, I)[J])
65 /* Test for an equality constraint. */
66 #define CSYS_IS_EQ(C, I) ((CSYS_ELT (C, I, 0)) == 0)
67 /* Test for an inequality constraint. */
68 #define CSYS_IS_INEQ(C, I) ((CSYS_ELT (C, I, 0)) != 0)
70 /* A generating system is composed of a set of rays, and lines. */
74 int dimension
, nb_lines
, nb_rays
;
76 /* RAYS is NB_RAYS lines by DIMENSION + 2 columns. */
81 #define GSYS_DIMENSION(P) ((P)->dimension)
82 #define GSYS_NB_LINES(P) ((P)->nb_lines)
83 #define GSYS_NB_RAYS(P) ((P)->nb_rays)
84 #define GSYS_M(P) ((P)->rays)
86 /* A polyhedron is described by two dual representations:
87 - a set of linear constraints, aka. constraint system,
88 - a set of rays and lines, aka. generating system.
91 typedef struct polyhedron
95 lambda_matrix saturation
;
98 #define POLYH_CSYS(P) (P->cy)
99 #define POLYH_GSYS(P) (P->gy)
100 #define POLYH_SAT(P) (P->saturation)
101 #define POLYH_CONS(P) CSYS_M (POLYH_CSYS (P))
102 #define POLYH_RAYS(P) GSYS_M (POLYH_GSYS (P))
103 #define POLYH_NB_RAYS(P) GSYS_NB_RAYS (POLYH_GSYS (P))
104 #define POLYH_NB_LINES(P) GSYS_NB_LINES (POLYH_GSYS (P))
105 #define POLYH_NB_CONS(P) CSYS_NB_CONSTRAINTS (POLYH_CSYS (P))
106 #define POLYH_DIM(P) CSYS_DIMENSION (POLYH_CSYS (P))
108 extern csys
csys_new (int, int, int);
109 extern csys
csys_copy (csys
);
110 extern void csys_print (FILE *, csys
);
111 extern void debug_csys (csys
);
112 extern omega_pb
csys_to_omega (csys
);
114 extern gsys
gsys_new (int, int, int);
115 extern gsys
gsys_copy (gsys
);
116 extern void gsys_print (FILE *, gsys
);
117 extern void debug_gsys (gsys
);
119 extern polyhedron
polyhedron_new (csys
, gsys
, lambda_matrix
);
120 extern polyhedron
polyhedron_from_csys (csys
);
121 extern polyhedron
polyhedron_from_gsys (gsys
);
122 extern polyhedron
polyhedron_copy (polyhedron
);
123 extern void polyhedron_print (FILE *, polyhedron
);
124 extern void debug_polyhedron (polyhedron
);
126 extern polyhedron
polyhedron_image (polyhedron
, lambda_matrix
, int, int);
127 extern polyhedron
polyhedron_preimage (polyhedron
, lambda_matrix
, int, int);
128 extern polyhedron
rays_to_polyhedron (lambda_matrix
, int, int);
129 extern polyhedron
cons_to_polyhedron (lambda_matrix
, int, int, int);