1 /* Lambda matrix and vector interface.
2 Copyright (C) 2003, 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
3 Contributed by Daniel Berlin <dberlin@dberlin.org>
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 3, 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 COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
26 /* An integer vector. A vector formally consists of an element of a vector
27 space. A vector space is a set that is closed under vector addition
28 and scalar multiplication. In this vector space, an element is a list of
30 typedef int *lambda_vector
;
32 DEF_VEC_P(lambda_vector
);
33 DEF_VEC_ALLOC_P(lambda_vector
,heap
);
35 /* An integer matrix. A matrix consists of m vectors of length n (IE
36 all vectors are the same length). */
37 typedef lambda_vector
*lambda_matrix
;
39 /* A transformation matrix, which is a self-contained ROWSIZE x COLSIZE
40 matrix. Rather than use floats, we simply keep a single DENOMINATOR that
41 represents the denominator for every element in the matrix. */
42 typedef struct lambda_trans_matrix_s
48 } *lambda_trans_matrix
;
49 #define LTM_MATRIX(T) ((T)->matrix)
50 #define LTM_ROWSIZE(T) ((T)->rowsize)
51 #define LTM_COLSIZE(T) ((T)->colsize)
52 #define LTM_DENOMINATOR(T) ((T)->denominator)
54 /* A vector representing a statement in the body of a loop.
55 The COEFFICIENTS vector contains a coefficient for each induction variable
56 in the loop nest containing the statement.
57 The DENOMINATOR represents the denominator for each coefficient in the
60 This structure is used during code generation in order to rewrite the old
61 induction variable uses in a statement in terms of the newly created
62 induction variables. */
63 typedef struct lambda_body_vector_s
65 lambda_vector coefficients
;
68 } *lambda_body_vector
;
69 #define LBV_COEFFICIENTS(T) ((T)->coefficients)
70 #define LBV_SIZE(T) ((T)->size)
71 #define LBV_DENOMINATOR(T) ((T)->denominator)
73 /* Piecewise linear expression.
74 This structure represents a linear expression with terms for the invariants
75 and induction variables of a loop.
76 COEFFICIENTS is a vector of coefficients for the induction variables, one
77 per loop in the loop nest.
78 CONSTANT is the constant portion of the linear expression
79 INVARIANT_COEFFICIENTS is a vector of coefficients for the loop invariants,
81 DENOMINATOR is the denominator for all of the coefficients and constants in
83 The linear expressions can be linked together using the NEXT field, in
84 order to represent MAX or MIN of a group of linear expressions. */
85 typedef struct lambda_linear_expression_s
87 lambda_vector coefficients
;
89 lambda_vector invariant_coefficients
;
91 struct lambda_linear_expression_s
*next
;
92 } *lambda_linear_expression
;
94 #define LLE_COEFFICIENTS(T) ((T)->coefficients)
95 #define LLE_CONSTANT(T) ((T)->constant)
96 #define LLE_INVARIANT_COEFFICIENTS(T) ((T)->invariant_coefficients)
97 #define LLE_DENOMINATOR(T) ((T)->denominator)
98 #define LLE_NEXT(T) ((T)->next)
102 lambda_linear_expression
lambda_linear_expression_new (int, int,
104 void print_lambda_linear_expression (FILE *, lambda_linear_expression
, int,
107 /* Loop structure. Our loop structure consists of a constant representing the
108 STEP of the loop, a set of linear expressions representing the LOWER_BOUND
109 of the loop, a set of linear expressions representing the UPPER_BOUND of
110 the loop, and a set of linear expressions representing the LINEAR_OFFSET of
111 the loop. The linear offset is a set of linear expressions that are
112 applied to *both* the lower bound, and the upper bound. */
113 typedef struct lambda_loop_s
115 lambda_linear_expression lower_bound
;
116 lambda_linear_expression upper_bound
;
117 lambda_linear_expression linear_offset
;
121 #define LL_LOWER_BOUND(T) ((T)->lower_bound)
122 #define LL_UPPER_BOUND(T) ((T)->upper_bound)
123 #define LL_LINEAR_OFFSET(T) ((T)->linear_offset)
124 #define LL_STEP(T) ((T)->step)
126 /* Loop nest structure.
127 The loop nest structure consists of a set of loop structures (defined
128 above) in LOOPS, along with an integer representing the DEPTH of the loop,
129 and an integer representing the number of INVARIANTS in the loop. Both of
130 these integers are used to size the associated coefficient vectors in the
131 linear expression structures. */
132 typedef struct lambda_loopnest_s
139 #define LN_LOOPS(T) ((T)->loops)
140 #define LN_DEPTH(T) ((T)->depth)
141 #define LN_INVARIANTS(T) ((T)->invariants)
143 lambda_loopnest
lambda_loopnest_new (int, int, struct obstack
*);
144 lambda_loopnest
lambda_loopnest_transform (lambda_loopnest
,
148 bool perfect_nest_p (struct loop
*);
149 void print_lambda_loopnest (FILE *, lambda_loopnest
, char);
151 #define lambda_loop_new() (lambda_loop) ggc_alloc_cleared (sizeof (struct lambda_loop_s))
153 void print_lambda_loop (FILE *, lambda_loop
, int, int, char);
155 lambda_matrix
lambda_matrix_new (int, int);
157 void lambda_matrix_id (lambda_matrix
, int);
158 bool lambda_matrix_id_p (lambda_matrix
, int);
159 void lambda_matrix_copy (lambda_matrix
, lambda_matrix
, int, int);
160 void lambda_matrix_negate (lambda_matrix
, lambda_matrix
, int, int);
161 void lambda_matrix_transpose (lambda_matrix
, lambda_matrix
, int, int);
162 void lambda_matrix_add (lambda_matrix
, lambda_matrix
, lambda_matrix
, int,
164 void lambda_matrix_add_mc (lambda_matrix
, int, lambda_matrix
, int,
165 lambda_matrix
, int, int);
166 void lambda_matrix_mult (lambda_matrix
, lambda_matrix
, lambda_matrix
,
168 void lambda_matrix_delete_rows (lambda_matrix
, int, int, int);
169 void lambda_matrix_row_exchange (lambda_matrix
, int, int);
170 void lambda_matrix_row_add (lambda_matrix
, int, int, int, int);
171 void lambda_matrix_row_negate (lambda_matrix mat
, int, int);
172 void lambda_matrix_row_mc (lambda_matrix
, int, int, int);
173 void lambda_matrix_col_exchange (lambda_matrix
, int, int, int);
174 void lambda_matrix_col_add (lambda_matrix
, int, int, int, int);
175 void lambda_matrix_col_negate (lambda_matrix
, int, int);
176 void lambda_matrix_col_mc (lambda_matrix
, int, int, int);
177 int lambda_matrix_inverse (lambda_matrix
, lambda_matrix
, int);
178 void lambda_matrix_hermite (lambda_matrix
, int, lambda_matrix
, lambda_matrix
);
179 void lambda_matrix_left_hermite (lambda_matrix
, int, int, lambda_matrix
, lambda_matrix
);
180 void lambda_matrix_right_hermite (lambda_matrix
, int, int, lambda_matrix
, lambda_matrix
);
181 int lambda_matrix_first_nz_vec (lambda_matrix
, int, int, int);
182 void lambda_matrix_project_to_null (lambda_matrix
, int, int, int,
184 void print_lambda_matrix (FILE *, lambda_matrix
, int, int);
186 lambda_trans_matrix
lambda_trans_matrix_new (int, int);
187 bool lambda_trans_matrix_nonsingular_p (lambda_trans_matrix
);
188 bool lambda_trans_matrix_fullrank_p (lambda_trans_matrix
);
189 int lambda_trans_matrix_rank (lambda_trans_matrix
);
190 lambda_trans_matrix
lambda_trans_matrix_basis (lambda_trans_matrix
);
191 lambda_trans_matrix
lambda_trans_matrix_padding (lambda_trans_matrix
);
192 lambda_trans_matrix
lambda_trans_matrix_inverse (lambda_trans_matrix
);
193 void print_lambda_trans_matrix (FILE *, lambda_trans_matrix
);
194 void lambda_matrix_vector_mult (lambda_matrix
, int, int, lambda_vector
,
196 bool lambda_trans_matrix_id_p (lambda_trans_matrix
);
198 lambda_body_vector
lambda_body_vector_new (int, struct obstack
*);
199 lambda_body_vector
lambda_body_vector_compute_new (lambda_trans_matrix
,
202 void print_lambda_body_vector (FILE *, lambda_body_vector
);
203 lambda_loopnest
gcc_loopnest_to_lambda_loopnest (struct loop
*,
207 void lambda_loopnest_to_gcc_loopnest (struct loop
*,
208 VEC(tree
,heap
) *, VEC(tree
,heap
) *,
209 lambda_loopnest
, lambda_trans_matrix
,
212 static inline void lambda_vector_negate (lambda_vector
, lambda_vector
, int);
213 static inline void lambda_vector_mult_const (lambda_vector
, lambda_vector
, int, int);
214 static inline void lambda_vector_add (lambda_vector
, lambda_vector
,
216 static inline void lambda_vector_add_mc (lambda_vector
, int, lambda_vector
, int,
218 static inline void lambda_vector_copy (lambda_vector
, lambda_vector
, int);
219 static inline bool lambda_vector_zerop (lambda_vector
, int);
220 static inline void lambda_vector_clear (lambda_vector
, int);
221 static inline bool lambda_vector_equal (lambda_vector
, lambda_vector
, int);
222 static inline int lambda_vector_min_nz (lambda_vector
, int, int);
223 static inline int lambda_vector_first_nz (lambda_vector
, int, int);
224 static inline void print_lambda_vector (FILE *, lambda_vector
, int);
226 /* Allocate a new vector of given SIZE. */
228 static inline lambda_vector
229 lambda_vector_new (int size
)
231 return GGC_CNEWVEC (int, size
);
236 /* Multiply vector VEC1 of length SIZE by a constant CONST1,
237 and store the result in VEC2. */
240 lambda_vector_mult_const (lambda_vector vec1
, lambda_vector vec2
,
241 int size
, int const1
)
246 lambda_vector_clear (vec2
, size
);
248 for (i
= 0; i
< size
; i
++)
249 vec2
[i
] = const1
* vec1
[i
];
252 /* Negate vector VEC1 with length SIZE and store it in VEC2. */
255 lambda_vector_negate (lambda_vector vec1
, lambda_vector vec2
,
258 lambda_vector_mult_const (vec1
, vec2
, size
, -1);
261 /* VEC3 = VEC1+VEC2, where all three the vectors are of length SIZE. */
264 lambda_vector_add (lambda_vector vec1
, lambda_vector vec2
,
265 lambda_vector vec3
, int size
)
268 for (i
= 0; i
< size
; i
++)
269 vec3
[i
] = vec1
[i
] + vec2
[i
];
272 /* VEC3 = CONSTANT1*VEC1 + CONSTANT2*VEC2. All vectors have length SIZE. */
275 lambda_vector_add_mc (lambda_vector vec1
, int const1
,
276 lambda_vector vec2
, int const2
,
277 lambda_vector vec3
, int size
)
280 for (i
= 0; i
< size
; i
++)
281 vec3
[i
] = const1
* vec1
[i
] + const2
* vec2
[i
];
284 /* Copy the elements of vector VEC1 with length SIZE to VEC2. */
287 lambda_vector_copy (lambda_vector vec1
, lambda_vector vec2
,
290 memcpy (vec2
, vec1
, size
* sizeof (*vec1
));
293 /* Return true if vector VEC1 of length SIZE is the zero vector. */
296 lambda_vector_zerop (lambda_vector vec1
, int size
)
299 for (i
= 0; i
< size
; i
++)
305 /* Clear out vector VEC1 of length SIZE. */
308 lambda_vector_clear (lambda_vector vec1
, int size
)
310 memset (vec1
, 0, size
* sizeof (*vec1
));
313 /* Return true if two vectors are equal. */
316 lambda_vector_equal (lambda_vector vec1
, lambda_vector vec2
, int size
)
319 for (i
= 0; i
< size
; i
++)
320 if (vec1
[i
] != vec2
[i
])
325 /* Return the minimum nonzero element in vector VEC1 between START and N.
326 We must have START <= N. */
329 lambda_vector_min_nz (lambda_vector vec1
, int n
, int start
)
334 gcc_assert (start
<= n
);
335 for (j
= start
; j
< n
; j
++)
338 if (min
< 0 || vec1
[j
] < vec1
[min
])
341 gcc_assert (min
>= 0);
346 /* Return the first nonzero element of vector VEC1 between START and N.
347 We must have START <= N. Returns N if VEC1 is the zero vector. */
350 lambda_vector_first_nz (lambda_vector vec1
, int n
, int start
)
353 while (j
< n
&& vec1
[j
] == 0)
359 /* Multiply a vector by a matrix. */
362 lambda_vector_matrix_mult (lambda_vector vect
, int m
, lambda_matrix mat
,
363 int n
, lambda_vector dest
)
366 lambda_vector_clear (dest
, n
);
367 for (i
= 0; i
< n
; i
++)
368 for (j
= 0; j
< m
; j
++)
369 dest
[i
] += mat
[j
][i
] * vect
[j
];
373 /* Print out a vector VEC of length N to OUTFILE. */
376 print_lambda_vector (FILE * outfile
, lambda_vector vector
, int n
)
380 for (i
= 0; i
< n
; i
++)
381 fprintf (outfile
, "%3d ", vector
[i
]);
382 fprintf (outfile
, "\n");
385 /* Compute the greatest common divisor of two numbers using
386 Euclid's algorithm. */
406 /* Compute the greatest common divisor of a VECTOR of SIZE numbers. */
409 lambda_vector_gcd (lambda_vector vector
, int size
)
417 for (i
= 1; i
< size
; i
++)
418 gcd1
= gcd (gcd1
, vector
[i
]);
423 /* Returns true when the vector V is lexicographically positive, in
424 other words, when the first nonzero element is positive. */
427 lambda_vector_lexico_pos (lambda_vector v
,
431 for (i
= 0; i
< n
; i
++)
443 /* Given a vector of induction variables IVS, and a vector of
444 coefficients COEFS, build a tree that is a linear combination of
445 the induction variables. */
448 build_linear_expr (tree type
, lambda_vector coefs
, VEC (tree
, heap
) *ivs
)
452 tree expr
= fold_convert (type
, integer_zero_node
);
454 for (i
= 0; VEC_iterate (tree
, ivs
, i
, iv
); i
++)
459 expr
= fold_build2 (PLUS_EXPR
, type
, expr
, iv
);
462 expr
= fold_build2 (PLUS_EXPR
, type
, expr
,
463 fold_build2 (MULT_EXPR
, type
, iv
,
464 build_int_cst (type
, k
)));
470 #endif /* LAMBDA_H */