1 /* Grid class implementation: simplify().
2 Copyright (C) 2001-2010 Roberto Bagnara <bagnara@cs.unipr.it>
3 Copyright (C) 2010-2016 BUGSENG srl (http://bugseng.com)
4
5 This file is part of the Parma Polyhedra Library (PPL).
6
7 The PPL is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by the
9 Free Software Foundation; either version 3 of the License, or (at your
10 option) any later version.
11
12 The PPL is distributed in the hope that it will be useful, but WITHOUT
13 ANY 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 this program; if not, write to the Free Software Foundation,
19 Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02111-1307, USA.
20
21 For the most up-to-date information see the Parma Polyhedra Library
22 site: http://bugseng.com/products/ppl/ . */
23
24 #include "ppl-config.h"
25 #include "assertions.hh"
26 #include "Grid_defs.hh"
27
28 namespace Parma_Polyhedra_Library {
29
30 void
reduce_line_with_line(Grid_Generator & row,Grid_Generator & pivot,dimension_type column)31 Grid::reduce_line_with_line(Grid_Generator& row, Grid_Generator& pivot,
32 dimension_type column) {
33 Coefficient_traits::const_reference pivot_column = pivot.expr.get(column);
34 Coefficient_traits::const_reference row_column = row.expr.get(column);
35 PPL_ASSERT(pivot_column != 0);
36 PPL_ASSERT(row_column != 0);
37
38 PPL_DIRTY_TEMP_COEFFICIENT(reduced_row_col);
39 // Use reduced_row_col temporarily to hold the gcd.
40 gcd_assign(reduced_row_col, pivot_column, row_column);
41 // Store the reduced ratio between pivot[column] and row[column].
42 PPL_DIRTY_TEMP_COEFFICIENT(reduced_pivot_col);
43 exact_div_assign(reduced_pivot_col, pivot_column, reduced_row_col);
44 exact_div_assign(reduced_row_col, row_column, reduced_row_col);
45 // Multiply row, then subtract from it a multiple of pivot such that
46 // the result in row[column] is zero.
47 neg_assign(reduced_row_col);
48 // pivot.space_dimension() is the index for the parameter divisor so we
49 // start reducing the line at index pivot.space_dimension() - 2.
50 row.expr.linear_combine(pivot.expr,
51 reduced_pivot_col, reduced_row_col,
52 column, pivot.expr.space_dimension());
53 PPL_ASSERT(row.OK());
54 PPL_ASSERT(row.expr.get(column) == 0);
55 }
56
57 void
reduce_equality_with_equality(Congruence & row,const Congruence & pivot,const dimension_type column)58 Grid::reduce_equality_with_equality(Congruence& row,
59 const Congruence& pivot,
60 const dimension_type column) {
61 // Assume two equalities.
62 PPL_ASSERT(row.modulus() == 0 && pivot.modulus() == 0);
63
64 Coefficient_traits::const_reference pivot_column = pivot.expr.get(column);
65 Coefficient_traits::const_reference row_column = row.expr.get(column);
66 PPL_ASSERT(pivot_column != 0);
67 PPL_ASSERT(row_column != 0);
68
69 PPL_DIRTY_TEMP_COEFFICIENT(reduced_row_col);
70 // Use reduced_row_col temporarily to hold the gcd.
71 gcd_assign(reduced_row_col, pivot_column, row_column);
72 // Store the reduced ratio between pivot[column] and row[column].
73 PPL_DIRTY_TEMP_COEFFICIENT(reduced_pivot_col);
74 exact_div_assign(reduced_pivot_col, pivot_column, reduced_row_col);
75 exact_div_assign(reduced_row_col, row_column, reduced_row_col);
76 // Multiply row, then subtract from it a multiple of pivot such that
77 // the result in row[column] is zero.
78 neg_assign(reduced_row_col);
79 row.expr.linear_combine(pivot.expr,
80 reduced_pivot_col, reduced_row_col,
81 0, column + 1);
82 PPL_ASSERT(row.OK());
83 PPL_ASSERT(row.expr.get(column) == 0);
84 }
85
86 template <typename R>
87 void
reduce_pc_with_pc(R & row,R & pivot,const dimension_type column,const dimension_type start,const dimension_type end)88 Grid::reduce_pc_with_pc(R& row, R& pivot,
89 const dimension_type column,
90 const dimension_type start,
91 const dimension_type end) {
92 PPL_ASSERT(start <= end);
93 PPL_ASSERT(start <= column);
94 PPL_ASSERT(column < end);
95
96 Linear_Expression& row_e = row.expr;
97 Linear_Expression& pivot_e = pivot.expr;
98
99 Coefficient_traits::const_reference pivot_column = pivot_e.get(column);
100 Coefficient_traits::const_reference row_column = row_e.get(column);
101 PPL_ASSERT(pivot_column != 0);
102 PPL_ASSERT(row_column != 0);
103
104 PPL_DIRTY_TEMP_COEFFICIENT(s);
105 PPL_DIRTY_TEMP_COEFFICIENT(t);
106 PPL_DIRTY_TEMP_COEFFICIENT(reduced_row_col);
107 PPL_DIRTY_TEMP_COEFFICIENT(gcd);
108 gcdext_assign(gcd, s, t, pivot_column, row_column);
109 PPL_ASSERT(pivot_e.get(column) * s + row_e.get(column) * t == gcd);
110
111 // Store the reduced ratio between pivot[column] and row[column].
112 PPL_DIRTY_TEMP_COEFFICIENT(reduced_pivot_col);
113 exact_div_assign(reduced_pivot_col, pivot_column, gcd);
114 exact_div_assign(reduced_row_col, row_column, gcd);
115
116 // Multiply row, then subtract from it a multiple of pivot such that
117 // the result in row[column] is zero. Afterward, multiply pivot,
118 // then add to it a (possibly negative) multiple of row such that
119 // the result in pivot[column] is the smallest possible positive
120 // integer.
121 const Linear_Expression old_pivot_e = pivot_e;
122 pivot_e.linear_combine_lax(row_e, s, t, start, end);
123 PPL_ASSERT(pivot_e.get(column) == gcd);
124 row_e.linear_combine(old_pivot_e, reduced_pivot_col, -reduced_row_col, start, end);
125 PPL_ASSERT(row_e.get(column) == 0);
126 }
127
128 void
reduce_parameter_with_line(Grid_Generator & row,const Grid_Generator & pivot,const dimension_type column,Swapping_Vector<Grid_Generator> & rows,const dimension_type total_num_columns)129 Grid::reduce_parameter_with_line(Grid_Generator& row,
130 const Grid_Generator& pivot,
131 const dimension_type column,
132 Swapping_Vector<Grid_Generator>& rows,
133 const dimension_type total_num_columns) {
134 // Very similar to reduce_congruence_with_equality below. Any
135 // change here may be needed there too.
136
137 Coefficient_traits::const_reference pivot_column = pivot.expr.get(column);
138 Coefficient_traits::const_reference row_column = row.expr.get(column);
139 PPL_ASSERT(pivot_column != 0);
140 PPL_ASSERT(row_column != 0);
141
142 // Subtract one to allow for the parameter divisor column
143 const dimension_type num_columns = total_num_columns - 1;
144
145 // If the elements at column in row and pivot are the same, then
146 // just subtract pivot from row.
147 if (row_column == pivot_column) {
148 row.expr.linear_combine(pivot.expr, 1, -1, 0, num_columns);
149 return;
150 }
151
152 PPL_DIRTY_TEMP_COEFFICIENT(reduced_row_col);
153 // Use reduced_row_col temporarily to hold the gcd.
154 gcd_assign(reduced_row_col, pivot_column, row_column);
155 // Store the reduced ratio between pivot[column] and row[column].
156 PPL_DIRTY_TEMP_COEFFICIENT(reduced_pivot_col);
157 exact_div_assign(reduced_pivot_col, pivot_column, reduced_row_col);
158 exact_div_assign(reduced_row_col, row_column, reduced_row_col);
159
160
161 // Since we are reducing the system to "strong minimal form",
162 // ensure that the multiplier is positive, so that the preceding
163 // diagonals (including the divisor) remain positive. It's safe to
164 // swap the signs as row[column] will still come out 0.
165 if (reduced_pivot_col < 0) {
166 neg_assign(reduced_pivot_col);
167 neg_assign(reduced_row_col);
168 }
169
170 // Multiply row such that a multiple of pivot can be subtracted from
171 // it below to render row[column] zero. This requires multiplying
172 // all other parameters to match.
173 for (dimension_type index = rows.size(); index-- > 0; ) {
174 Grid_Generator& gen = rows[index];
175 if (gen.is_parameter_or_point()) {
176 // Do not scale the last coefficient.
177 gen.expr.mul_assign(reduced_pivot_col, 0, num_columns);
178 }
179 }
180
181 // Subtract from row a multiple of pivot such that the result in
182 // row[column] is zero.
183 row.expr.linear_combine(pivot.expr,
184 Coefficient_one(), -reduced_row_col,
185 column, num_columns);
186 PPL_ASSERT(row.expr.get(column) == 0);
187 }
188
189 void
reduce_congruence_with_equality(Congruence & row,const Congruence & pivot,const dimension_type column,Swapping_Vector<Congruence> & sys)190 Grid::reduce_congruence_with_equality(Congruence& row,
191 const Congruence& pivot,
192 const dimension_type column,
193 Swapping_Vector<Congruence>& sys) {
194 // Very similar to reduce_parameter_with_line above. Any change
195 // here may be needed there too.
196 PPL_ASSERT(row.modulus() > 0 && pivot.modulus() == 0);
197
198 Coefficient_traits::const_reference pivot_column = pivot.expr.get(column);
199 Coefficient_traits::const_reference row_column = row.expr.get(column);
200
201 // If the elements at `column' in row and pivot are the same, then
202 // just subtract `pivot' from `row'.
203 if (row_column == pivot_column) {
204 row.expr -= pivot.expr;
205 return;
206 }
207
208 PPL_DIRTY_TEMP_COEFFICIENT(reduced_row_col);
209 // Use reduced_row_col temporarily to hold the gcd.
210 gcd_assign(reduced_row_col, pivot_column, row_column);
211 PPL_DIRTY_TEMP_COEFFICIENT(reduced_pivot_col);
212 exact_div_assign(reduced_pivot_col, pivot_column, reduced_row_col);
213 exact_div_assign(reduced_row_col, row_column, reduced_row_col);
214 // Ensure that `reduced_pivot_col' is positive, so that the modulus
215 // remains positive when multiplying the proper congruences below.
216 // It's safe to swap the signs as row[column] will still come out 0.
217 if (reduced_pivot_col < 0) {
218 neg_assign(reduced_pivot_col);
219 neg_assign(reduced_row_col);
220 }
221 // Multiply `row', including the modulus, by reduced_pivot_col. To
222 // keep all the moduli the same this requires multiplying all the
223 // other proper congruences in the same way.
224 for (dimension_type index = sys.size(); index-- > 0; ) {
225 Congruence& cg = sys[index];
226 if (cg.is_proper_congruence()) {
227 cg.scale(reduced_pivot_col);
228 }
229 }
230 // Subtract from row a multiple of pivot such that the result in
231 // row[column] is zero.
232 sub_mul_assign(row.expr, reduced_row_col, pivot.expr);
233 PPL_ASSERT(row.expr.get(column) == 0);
234 }
235
236 #ifndef NDEBUG
237 template <typename M, typename R>
238 bool
rows_are_zero(M & system,dimension_type first,dimension_type last,dimension_type row_size)239 Grid::rows_are_zero(M& system, dimension_type first,
240 dimension_type last, dimension_type row_size) {
241 while (first <= last) {
242 const R& row = system[first++];
243 if (!row.expr.all_zeroes(0, row_size)) {
244 return false;
245 }
246 }
247 return true;
248 }
249 #endif
250
251 void
simplify(Grid_Generator_System & ggs,Dimension_Kinds & dim_kinds)252 Grid::simplify(Grid_Generator_System& ggs, Dimension_Kinds& dim_kinds) {
253 PPL_ASSERT(!ggs.has_no_rows());
254 // Changes here may also be required in the congruence version below.
255
256 // Subtract one to allow for the parameter divisor column
257 const dimension_type num_columns = ggs.space_dimension() + 1;
258
259 if (dim_kinds.size() != num_columns) {
260 dim_kinds.resize(num_columns);
261 }
262
263 const dimension_type num_rows = ggs.num_rows();
264
265 // For each dimension `dim' move or construct a row into position
266 // `pivot_index' such that the row has zero in all elements
267 // following column `dim' and a value other than zero in column
268 // `dim'.
269 dimension_type pivot_index = 0;
270 for (dimension_type dim = 0; dim < num_columns; ++dim) {
271 // Consider the pivot and following rows.
272 dimension_type row_index = pivot_index;
273
274 // Move down over rows which have zero in column `dim'.
275 while (row_index < num_rows
276 && ggs.sys.rows[row_index].expr.get(dim) == 0) {
277 ++row_index;
278 }
279
280 if (row_index == num_rows) {
281 // Element in column `dim' is zero in all rows from the pivot.
282 dim_kinds[dim] = GEN_VIRTUAL;
283 }
284 else {
285 if (row_index != pivot_index) {
286 using std::swap;
287 swap(ggs.sys.rows[row_index], ggs.sys.rows[pivot_index]);
288 }
289 Grid_Generator& pivot = ggs.sys.rows[pivot_index];
290 bool pivot_is_line = pivot.is_line();
291
292 // Change the matrix so that the value at `dim' in every row
293 // following `pivot_index' is 0, leaving an equivalent grid.
294 while (row_index < num_rows - 1) {
295 ++row_index;
296 Grid_Generator& row = ggs.sys.rows[row_index];
297
298 if (row.expr.get(dim) == 0) {
299 continue;
300 }
301
302 if (row.is_line()) {
303 if (pivot_is_line) {
304 reduce_line_with_line(row, pivot, dim);
305 }
306 else {
307 PPL_ASSERT(pivot.is_parameter_or_point());
308 using std::swap;
309 swap(row, pivot);
310 pivot_is_line = true;
311 reduce_parameter_with_line(row, pivot, dim, ggs.sys.rows,
312 num_columns + 1);
313 }
314 }
315 else {
316 PPL_ASSERT(row.is_parameter_or_point());
317 if (pivot_is_line) {
318 reduce_parameter_with_line(row, pivot, dim, ggs.sys.rows,
319 num_columns + 1);
320 }
321 else {
322 PPL_ASSERT(pivot.is_parameter_or_point());
323 reduce_pc_with_pc(row, pivot, dim, dim, num_columns);
324 }
325 }
326 }
327
328 if (pivot_is_line) {
329 dim_kinds[dim] = LINE;
330 }
331 else {
332 PPL_ASSERT(pivot.is_parameter_or_point());
333 dim_kinds[dim] = PARAMETER;
334 }
335
336 // Since we are reducing the system to "strong minimal form",
337 // ensure that a positive value follows the leading zeros.
338 if (pivot.expr.get(dim) < 0) {
339 pivot.expr.negate(dim, num_columns);
340 }
341
342 // Factor this row out of the preceding rows.
343 reduce_reduced<Grid_Generator_System>
344 (ggs.sys.rows, dim, pivot_index, dim, num_columns - 1, dim_kinds);
345
346 ++pivot_index;
347 }
348 }
349
350 // Clip any zero rows from the end of the matrix.
351 if (num_rows > pivot_index) {
352 #ifndef NDEBUG
353 const bool ret = rows_are_zero<Grid_Generator_System, Grid_Generator>
354 (ggs,
355 // index of first
356 pivot_index,
357 // index of last
358 ggs.num_rows() - 1,
359 // row size
360 ggs.space_dimension() + 1);
361 PPL_ASSERT(ret == true);
362 #endif
363 ggs.sys.rows.resize(pivot_index);
364 }
365
366 // Ensure that the parameter divisors are the same as the system
367 // divisor.
368 const Coefficient& system_divisor = ggs.sys.rows[0].expr.inhomogeneous_term();
369 for (dimension_type i = ggs.sys.rows.size() - 1,
370 dim = num_columns - 1; dim > 0; --dim) {
371 switch (dim_kinds[dim]) {
372 case PARAMETER:
373 ggs.sys.rows[i].set_divisor(system_divisor);
374 // Intentionally fall through.
375 case LINE:
376 PPL_ASSERT(ggs.sys.rows[i].OK());
377 --i;
378 break;
379 case GEN_VIRTUAL:
380 break;
381 }
382 }
383
384 ggs.unset_pending_rows();
385 PPL_ASSERT(ggs.sys.OK());
386 }
387
388 bool
simplify(Congruence_System & cgs,Dimension_Kinds & dim_kinds)389 Grid::simplify(Congruence_System& cgs, Dimension_Kinds& dim_kinds) {
390 PPL_ASSERT(cgs.space_dimension() != 0);
391 // Changes here may also be required in the generator version above.
392
393 // TODO: Consider normalizing the moduli only when congruences are
394 // added to con_sys.
395 cgs.normalize_moduli();
396
397 // NOTE: add one for the inhomogeneous term (but not the modulus).
398 const dimension_type num_columns = cgs.space_dimension() + 1;
399
400 if (dim_kinds.size() != num_columns) {
401 dim_kinds.resize(num_columns);
402 }
403
404 const dimension_type num_rows = cgs.num_rows();
405
406 // For each dimension `dim' move or construct a row into position
407 // `pivot_index' such that the row has a value of zero in all
408 // elements preceding column `dim' and some other value in column
409 // `dim'.
410 dimension_type pivot_index = 0;
411 for (dimension_type dim = num_columns; dim-- > 0; ) {
412 // Consider the pivot and following rows.
413 dimension_type row_index = pivot_index;
414
415 // Move down over rows which have zero in column `dim'.
416 while (row_index < num_rows && cgs.rows[row_index].expr.get(dim) == 0) {
417 ++row_index;
418 }
419
420 if (row_index == num_rows) {
421 // Element in column `dim' is zero in all rows from the pivot,
422 // or `cgs' is empty of rows.
423 dim_kinds[dim] = CON_VIRTUAL;
424 }
425 else {
426 // Here row_index != num_rows.
427 if (row_index != pivot_index) {
428 using std::swap;
429 swap(cgs.rows[row_index], cgs.rows[pivot_index]);
430 }
431
432 Congruence& pivot = cgs.rows[pivot_index];
433 bool pivot_is_equality = pivot.is_equality();
434
435 // Change the matrix so that the value at `dim' in every row
436 // following `pivot_index' is 0, leaving an equivalent grid.
437 while (row_index < num_rows - 1) {
438 ++row_index;
439 Congruence& row = cgs.rows[row_index];
440 if (row.expr.get(dim) == 0) {
441 continue;
442 }
443
444 if (row.is_equality()) {
445 if (pivot_is_equality) {
446 reduce_equality_with_equality(row, pivot, dim);
447 }
448 else {
449 PPL_ASSERT(pivot.is_proper_congruence());
450 using std::swap;
451 swap(row, pivot);
452 pivot_is_equality = true;
453 reduce_congruence_with_equality(row, pivot, dim, cgs.rows);
454 }
455 }
456 else {
457 PPL_ASSERT(row.is_proper_congruence());
458 if (pivot_is_equality) {
459 reduce_congruence_with_equality(row, pivot, dim, cgs.rows);
460 }
461 else {
462 PPL_ASSERT(pivot.is_proper_congruence());
463 reduce_pc_with_pc(row, pivot, dim, 0, dim + 1);
464 }
465 }
466 }
467
468 if (pivot_is_equality) {
469 dim_kinds[dim] = EQUALITY;
470 }
471 else {
472 PPL_ASSERT(pivot.is_proper_congruence());
473 dim_kinds[dim] = PROPER_CONGRUENCE;
474 }
475
476 // Since we are reducing the system to "strong minimal form",
477 // ensure that a positive value follows the leading zeros.
478 if (pivot.expr.get(dim) < 0) {
479 pivot.expr.negate(0, dim + 1);
480 }
481
482 // Factor this row out of the preceding ones.
483 reduce_reduced<Congruence_System>
484 (cgs.rows, dim, pivot_index, 0, dim, dim_kinds, false);
485
486 PPL_ASSERT(cgs.OK());
487
488 ++pivot_index;
489 }
490 }
491
492 if (pivot_index > 0) {
493 // If the last row is false then make it the equality 1 = 0, and
494 // make it the only row.
495
496 #ifndef NDEBUG
497 {
498 const bool ret = rows_are_zero<Congruence_System, Congruence>
499 (cgs,
500 // index of first
501 pivot_index,
502 // index of last
503 num_rows - 1,
504 // row size
505 num_columns);
506 PPL_ASSERT(ret == true);
507 }
508 #endif
509
510 cgs.remove_trailing_rows(num_rows - pivot_index);
511 Congruence& last_row = cgs.rows.back();
512
513 switch (dim_kinds[0]) {
514
515 case PROPER_CONGRUENCE:
516 if (last_row.inhomogeneous_term() % last_row.modulus() == 0) {
517 break;
518 }
519 // The last row is a false proper congruence.
520 last_row.set_modulus(Coefficient_zero());
521 dim_kinds[0] = EQUALITY;
522 // Intentionally fall through.
523
524 case EQUALITY:
525 // The last row is a false equality, as all the coefficient terms
526 // are zero while the inhomogeneous term (as a result of the
527 // reduced form) is some other value.
528 last_row.expr.set_inhomogeneous_term(Coefficient_one());
529 dim_kinds.resize(1);
530 using std::swap;
531 swap(cgs.rows[0], last_row);
532 cgs.remove_trailing_rows(cgs.num_rows() - 1);
533 PPL_ASSERT(cgs.OK());
534 return true;
535
536 default:
537 break;
538 }
539 }
540 else {
541 // Either `cgs' is empty (it defines the universe) or every column
542 // before the modulus column contains only zeroes.
543
544 if (num_rows > 0) {
545 #ifndef NDEBUG
546 const bool ret = rows_are_zero<Congruence_System, Congruence>
547 (cgs,
548 // index of first
549 0,
550 // index of last
551 num_rows - 1,
552 // row size
553 num_columns);
554 PPL_ASSERT(ret == true);
555 #endif
556 // Ensure that a single row will remain for the integrality congruence.
557 cgs.remove_trailing_rows(num_rows - 1);
558 }
559
560 // Set up the integrality congruence.
561 dim_kinds[0] = PROPER_CONGRUENCE;
562 if (num_rows == 0) {
563 Congruence cg;
564 cg.set_modulus(Coefficient_one());
565 cg.set_space_dimension(cgs.space_dimension());
566 cg.expr.set_inhomogeneous_term(Coefficient_one());
567 cgs.insert_verbatim(cg, Recycle_Input());
568
569 PPL_ASSERT(cgs.OK());
570 return false;
571 }
572
573 PPL_ASSERT(cgs.num_rows() == 1);
574 cgs.rows.back().set_modulus(Coefficient_one());
575 }
576
577 // Ensure that the last row is the integrality congruence.
578 if (dim_kinds[0] == CON_VIRTUAL) {
579 // The last row is virtual, append the integrality congruence.
580 dim_kinds[0] = PROPER_CONGRUENCE;
581 Congruence new_last_row;
582 new_last_row.set_space_dimension(cgs.space_dimension());
583 new_last_row.set_modulus(Coefficient_one());
584 // Try use an existing modulus.
585 dimension_type row_index = cgs.num_rows();
586 while (row_index-- > 0) {
587 const Congruence& row = cgs[row_index];
588 if (row.modulus() > 0) {
589 new_last_row.set_modulus(row.modulus());
590 break;
591 }
592 }
593 new_last_row.expr.set_inhomogeneous_term(new_last_row.modulus());
594 cgs.insert_verbatim(new_last_row, Recycle_Input());
595 }
596 else {
597 cgs.rows.back().expr.set_inhomogeneous_term(cgs.rows.back().modulus());
598 }
599
600 // Since we are reducing the system to "strong minimal form",
601 // factor the modified integrality congruence out of the other rows;
602 reduce_reduced<Congruence_System>
603 (cgs.rows, 0, cgs.num_rows() - 1, 0, 0, dim_kinds, false);
604
605 PPL_ASSERT(cgs.OK());
606 return false;
607 }
608
609 } // namespace Parma_Polyhedra_Library
610