old-autovect-branch/gcc/polyhedron.h

   1 /* Structure of polyhedra.
   2    Copyright (C) 2005 Free Software Foundation, Inc.
   3    Contributed by Sebastian Pop <sebastian.pop@cri.ensmp.fr>
   4
   5 This file is part of GCC.
   6
   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
  10 version.
  11
  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
  15 for more details.
  16
  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
  20 02111-1307, USA.  */
  21
  22 #ifndef GCC_POLYHEDRON_H
  23 #define GCC_POLYHEDRON_H
  24
  25 #include "lambda.h"
  26 #include "omega.h"
  27
  28 /* A constraint system is composed of a system of linear equalities
  29    and inequalities.  Example: the following constraints system
  30
  31    0  = x + 0y + 5z + 9
  32    0 <= x + 2y + 3z - 8
  33
  34    is encoded by the matrix:
  35
  36    |IS_INEQ  VECTORS  CST
  37    |   0      1 0 5    9
  38    |   1      1 2 3   -8
  39 */
  40
  41 typedef struct csys
  42 {
  43   /* NB_CONSTRAINTS = NB_EQS + nb_ineqs.  */
  44   int dimension, nb_eqs, nb_constraints;
  45
  46   /* CONSTRAINTS is NB_CONSTRAINTS lines by DIMENSION + 2 columns.  */
  47   lambda_matrix constraints;
  48
  49 } *csys;
  50
  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)
  54
  55 /* The raw matrix.  */
  56 #define CSYS_M(C) ((C)->constraints)
  57 /* An element.  */
  58 #define CSYS_ELT(C, I, J) (CSYS_M (C)[I][J])
  59 /* The constant.  */
  60 #define CSYS_CST(C, I) (CSYS_ELT (C, I, CSYS_DIMENSION (C) + 1))
  61 /* The vector.  */
  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)
  69
  70 /* A generating system is composed of a set of rays, and lines.  */
  71
  72 typedef struct gsys
  73 {
  74   int dimension, nb_lines, nb_rays;
  75
  76   /* RAYS is NB_RAYS lines by DIMENSION + 2 columns.  */
  77   lambda_matrix rays;
  78
  79 } *gsys;
  80
  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)
  85
  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.
  89 */
  90
  91 typedef struct polyhedron
  92 {
  93   csys cy;
  94   gsys gy;
  95   lambda_matrix saturation;
  96 } *polyhedron;
  97
  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))
 107
 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);
 113
 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);
 118
 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);
 125
 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);
 130
 131 #endif