1 /* Grid class implementation
2 (non-inline widening-related member functions).
3 Copyright (C) 2001-2010 Roberto Bagnara <bagnara@cs.unipr.it>
4 Copyright (C) 2010-2016 BUGSENG srl (http://bugseng.com)
5
6 This file is part of the Parma Polyhedra Library (PPL).
7
8 The PPL is free software; you can redistribute it and/or modify it
9 under the terms of the GNU General Public License as published by the
10 Free Software Foundation; either version 3 of the License, or (at your
11 option) any later version.
12
13 The PPL is distributed in the hope that it will be useful, but WITHOUT
14 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 for more details.
17
18 You should have received a copy of the GNU General Public License
19 along with this program; if not, write to the Free Software Foundation,
20 Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02111-1307, USA.
21
22 For the most up-to-date information see the Parma Polyhedra Library
23 site: http://bugseng.com/products/ppl/ . */
24
25 #include "ppl-config.h"
26 #include "Grid_defs.hh"
27 #include "assertions.hh"
28 #include <iostream>
29
30 namespace PPL = Parma_Polyhedra_Library;
31
32 void
select_wider_congruences(const Grid & y,Congruence_System & selected_cgs) const33 PPL::Grid::select_wider_congruences(const Grid& y,
34 Congruence_System& selected_cgs) const {
35 // Private method: the caller must ensure the following conditions
36 // (beside the inclusion `y <= x').
37 PPL_ASSERT(space_dim == y.space_dim);
38 PPL_ASSERT(!marked_empty());
39 PPL_ASSERT(!y.marked_empty());
40 PPL_ASSERT(congruences_are_minimized());
41 PPL_ASSERT(y.congruences_are_minimized());
42
43 // Note: row counters start at 0, to preserve the original order in
44 // the selected congruences.
45 for (dimension_type dim = con_sys.space_dimension(), x_row = 0, y_row = 0;
46 dim > 0; --dim) {
47 PPL_ASSERT(dim_kinds[dim] == CON_VIRTUAL
48 || dim_kinds[dim] == y.dim_kinds[dim]);
49 switch (dim_kinds[dim]) {
50 case PROPER_CONGRUENCE:
51 {
52 const Congruence& cg = con_sys[x_row];
53 const Congruence& y_cg = y.con_sys[y_row];
54 if (cg.is_equal_at_dimension(Variable(dim - 1), y_cg)) {
55 // The leading diagonal entries are equal.
56 selected_cgs.insert(cg);
57 }
58 ++x_row;
59 ++y_row;
60 }
61 break;
62 case EQUALITY:
63 selected_cgs.insert(con_sys[x_row]);
64 ++x_row;
65 ++y_row;
66 break;
67 case CON_VIRTUAL:
68 if (y.dim_kinds[dim] != CON_VIRTUAL) {
69 ++y_row;
70 }
71 break;
72 }
73 }
74 }
75
76 void
congruence_widening_assign(const Grid & y,unsigned * tp)77 PPL::Grid::congruence_widening_assign(const Grid& y, unsigned* tp) {
78 Grid& x = *this;
79 // Dimension-compatibility check.
80 if (x.space_dim != y.space_dim) {
81 throw_dimension_incompatible("widening_assign(y)", "y", y);
82 }
83
84 // Assume `y' is contained in or equal to `x'.
85 PPL_EXPECT_HEAVY(copy_contains(x, y));
86
87 // Leave `x' the same if `x' or `y' is zero-dimensional or empty.
88 if (x.space_dim == 0 || x.marked_empty() || y.marked_empty()) {
89 return;
90 }
91
92 // Ensure that the `x' congruences are in minimal form.
93 if (x.congruences_are_up_to_date()) {
94 if (!x.congruences_are_minimized()) {
95 if (simplify(x.con_sys, x.dim_kinds)) {
96 // `x' is empty.
97 x.set_empty();
98 return;
99 }
100 x.set_congruences_minimized();
101 }
102 }
103 else {
104 x.update_congruences();
105 }
106
107 // Ensure that the `y' congruences are in minimal form.
108 Grid& yy = const_cast<Grid&>(y);
109 if (yy.congruences_are_up_to_date()) {
110 if (!yy.congruences_are_minimized()) {
111 if (simplify(yy.con_sys, yy.dim_kinds)) {
112 // `y' is empty.
113 yy.set_empty();
114 return;
115 }
116 yy.set_congruences_minimized();
117 }
118 }
119 else {
120 yy.update_congruences();
121 }
122
123 if (con_sys.num_equalities() < yy.con_sys.num_equalities()) {
124 return;
125 }
126 // Copy into `cgs' the congruences of `x' that are common to `y',
127 // according to the grid widening.
128 Congruence_System cgs;
129 x.select_wider_congruences(yy, cgs);
130
131 if (cgs.num_rows() == con_sys.num_rows()) {
132 // All congruences were selected, thus the result is `x'.
133 return;
134 }
135
136 // A strict subset of the congruences was selected.
137
138 Grid result(x.space_dim);
139 result.add_recycled_congruences(cgs);
140
141 // Check whether we are using the widening-with-tokens technique
142 // and there are still tokens available.
143 if (tp != 0 && *tp > 0) {
144 // There are tokens available. If `result' is not a subset of
145 // `x', then it is less precise and we use one of the available
146 // tokens.
147 if (!x.contains(result)) {
148 --(*tp);
149 }
150 }
151 else {
152 // No tokens.
153 x.m_swap(result);
154 }
155
156 PPL_ASSERT(x.OK(true));
157 }
158
159 void
limited_congruence_extrapolation_assign(const Grid & y,const Congruence_System & cgs,unsigned * tp)160 PPL::Grid::limited_congruence_extrapolation_assign(const Grid& y,
161 const Congruence_System& cgs,
162 unsigned* tp) {
163 Grid& x = *this;
164
165 // Check dimension compatibility.
166 if (x.space_dim != y.space_dim) {
167 throw_dimension_incompatible("limited_extrapolation_assign(y, cgs)",
168 "y", y);
169 }
170 // `cgs' must be dimension-compatible with the two grids.
171 const dimension_type cgs_space_dim = cgs.space_dimension();
172 if (x.space_dim < cgs_space_dim) {
173 throw_dimension_incompatible("limited_extrapolation_assign(y, cgs)",
174 "cgs", cgs);
175 }
176
177 const dimension_type cgs_num_rows = cgs.num_rows();
178 // If `cgs' is empty (of rows), fall back to ordinary widening.
179 if (cgs_num_rows == 0) {
180 x.widening_assign(y, tp);
181 return;
182 }
183
184 // Assume `y' is contained in or equal to `x'.
185 PPL_EXPECT_HEAVY(copy_contains(x, y));
186
187 if (y.marked_empty()) {
188 return;
189 }
190 if (x.marked_empty()) {
191 return;
192 }
193
194 // The limited widening between two grids in a zero-dimensional
195 // space is also a grid in a zero-dimensional space.
196 if (x.space_dim == 0) {
197 return;
198 }
199
200 // Update the generators of `x': these are used to select, from the
201 // congruences in `cgs', those that must be added to the widened
202 // grid.
203 if (!x.generators_are_up_to_date() && !x.update_generators()) {
204 // `x' is empty.
205 return;
206 }
207
208 if (tp == NULL || *tp == 0) {
209 // Widening may change the grid, so add the congruences.
210 Congruence_System new_cgs;
211 // The congruences to be added need only be satisfied by all the
212 // generators of `x', as `y <= x'. Iterate upwards here, to keep
213 // the relative ordering of congruences (just for aesthetics).
214 for (dimension_type i = 0; i < cgs_num_rows; ++i) {
215 const Congruence& cg = cgs[i];
216 if (x.relation_with(cg) == Poly_Con_Relation::is_included()) {
217 new_cgs.insert(cg);
218 }
219 }
220 x.congruence_widening_assign(y, tp);
221 x.add_recycled_congruences(new_cgs);
222 }
223 else {
224 // There are tokens, so widening will leave the grid the same.
225 x.congruence_widening_assign(y, tp);
226 }
227
228 PPL_ASSERT(OK());
229 }
230
231 void
select_wider_generators(const Grid & y,Grid_Generator_System & widened_ggs) const232 PPL::Grid::select_wider_generators(const Grid& y,
233 Grid_Generator_System& widened_ggs) const {
234 // Private method: the caller must ensure the following conditions
235 // (beside the inclusion `y <= x').
236 PPL_ASSERT(space_dim == y.space_dim);
237 PPL_ASSERT(!marked_empty());
238 PPL_ASSERT(!y.marked_empty());
239 PPL_ASSERT(generators_are_minimized());
240 PPL_ASSERT(y.generators_are_minimized());
241
242 // Note: row counters start at 0, to preserve the original order in
243 // the selected generators.
244 for (dimension_type dim = 0, x_row = 0, y_row = 0;
245 dim <= gen_sys.space_dimension(); ++dim) {
246 PPL_ASSERT(dim_kinds[dim] == LINE
247 || y.dim_kinds[dim] == GEN_VIRTUAL
248 || dim_kinds[dim] == y.dim_kinds[dim]);
249 switch (dim_kinds[dim]) {
250 case PARAMETER:
251 {
252 const Grid_Generator& gg = gen_sys[x_row];
253 const Grid_Generator& y_gg = y.gen_sys[y_row];
254 if (gg.is_equal_at_dimension(dim, y_gg)) {
255 // The leading diagonal entry is equal.
256 widened_ggs.insert(gg);
257 }
258 else {
259 const Linear_Expression expr(gg.expression());
260 Grid_Generator line = grid_line(expr);
261 widened_ggs.insert(line, Recycle_Input());
262 }
263 ++x_row;
264 ++y_row;
265 }
266 break;
267 case LINE:
268 widened_ggs.insert(gen_sys[x_row]);
269 ++x_row;
270 ++y_row;
271 break;
272 case GEN_VIRTUAL:
273 if (y.dim_kinds[dim] != GEN_VIRTUAL) {
274 ++y_row;
275 }
276 break;
277 }
278 }
279 }
280
281 void
generator_widening_assign(const Grid & y,unsigned * tp)282 PPL::Grid::generator_widening_assign(const Grid& y, unsigned* tp) {
283 Grid& x = *this;
284
285 // Dimension-compatibility check.
286 if (x.space_dim != y.space_dim) {
287 throw_dimension_incompatible("generator_widening_assign(y)", "y", y);
288 }
289
290 // Assume `y' is contained in or equal to `x'.
291 PPL_EXPECT_HEAVY(copy_contains(x, y));
292
293 // Leave `x' the same if `x' or `y' is zero-dimensional or empty.
294 if (x.space_dim == 0 || x.marked_empty() || y.marked_empty()) {
295 return;
296 }
297
298 // Ensure that the `x' generators are in minimal form.
299 if (x.generators_are_up_to_date()) {
300 if (!x.generators_are_minimized()) {
301 simplify(x.gen_sys, x.dim_kinds);
302 PPL_ASSERT(!x.gen_sys.has_no_rows());
303 x.set_generators_minimized();
304 }
305 }
306 else {
307 x.update_generators();
308 }
309
310 if (x.marked_empty()) {
311 return;
312 }
313
314 // Ensure that the `y' generators are in minimal form.
315 Grid& yy = const_cast<Grid&>(y);
316 if (yy.generators_are_up_to_date()) {
317 if (!yy.generators_are_minimized()) {
318 simplify(yy.gen_sys, yy.dim_kinds);
319 PPL_ASSERT(!yy.gen_sys.has_no_rows());
320 yy.set_generators_minimized();
321 }
322 }
323 else {
324 yy.update_generators();
325 }
326
327 if (gen_sys.num_rows() > yy.gen_sys.num_rows()) {
328 return;
329 }
330
331 if (gen_sys.num_lines() > yy.gen_sys.num_lines()) {
332 return;
333 }
334
335 // Copy into `ggs' the generators of `x' that are common to `y',
336 // according to the grid widening.
337 Grid_Generator_System ggs;
338 x.select_wider_generators(yy, ggs);
339
340 if (ggs.num_parameters() == gen_sys.num_parameters()) {
341 // All parameters are kept as parameters, thus the result is `x'.
342 return;
343 }
344
345 // A strict subset of the parameters was selected.
346
347 Grid result(x.space_dim, EMPTY);
348 result.add_recycled_grid_generators(ggs);
349
350 // Check whether we are using the widening-with-tokens technique
351 // and there are still tokens available.
352 if (tp != 0 && *tp > 0) {
353 // There are tokens available. If `result' is not a subset of
354 // `x', then it is less precise and we use one of the available
355 // tokens.
356 if (!x.contains(result)) {
357 --(*tp);
358 }
359 }
360 else {
361 // No tokens.
362 x.m_swap(result);
363 }
364
365 PPL_ASSERT(x.OK(true));
366 }
367
368 void
limited_generator_extrapolation_assign(const Grid & y,const Congruence_System & cgs,unsigned * tp)369 PPL::Grid::limited_generator_extrapolation_assign(const Grid& y,
370 const Congruence_System& cgs,
371 unsigned* tp) {
372 Grid& x = *this;
373
374 // Check dimension compatibility.
375 if (x.space_dim != y.space_dim) {
376 throw_dimension_incompatible("limited_extrapolation_assign(y, cgs)",
377 "y", y);
378 }
379 // `cgs' must be dimension-compatible with the two grids.
380 const dimension_type cgs_space_dim = cgs.space_dimension();
381 if (x.space_dim < cgs_space_dim) {
382 throw_dimension_incompatible("limited_extrapolation_assign(y, cgs)",
383 "cgs", cgs);
384 }
385
386 const dimension_type cgs_num_rows = cgs.num_rows();
387 // If `cgs' is empty (of rows), fall back to ordinary widening.
388 if (cgs_num_rows == 0) {
389 x.generator_widening_assign(y, tp);
390 return;
391 }
392
393 // Assume `y' is contained in or equal to `x'.
394 PPL_EXPECT_HEAVY(copy_contains(x, y));
395
396 if (y.marked_empty()) {
397 return;
398 }
399 if (x.marked_empty()) {
400 return;
401 }
402
403 // The limited widening between two grids in a zero-dimensional
404 // space is also a grid in a zero-dimensional space.
405 if (x.space_dim == 0) {
406 return;
407 }
408
409 // Update the generators of `x': these are used to select, from the
410 // congruences in `cgs', those that must be added to the widened
411 // grid.
412 if (!x.generators_are_up_to_date() && !x.update_generators()) {
413 // `x' is empty.
414 return;
415 }
416
417 if (tp == NULL || *tp == 0) {
418 // Widening may change the grid, so add the congruences.
419 Congruence_System new_cgs;
420 // The congruences to be added need only be satisfied by all the
421 // generators of `x', as `y <= x'. Iterate upwards here, to keep
422 // the relative ordering of congruences (just for aesthetics).
423 for (dimension_type i = 0; i < cgs_num_rows; ++i) {
424 const Congruence& cg = cgs[i];
425 if (x.relation_with(cg) == Poly_Con_Relation::is_included()) {
426 new_cgs.insert(cg);
427 }
428 }
429 x.generator_widening_assign(y, tp);
430 x.add_recycled_congruences(new_cgs);
431 }
432 else {
433 // There are tokens, so widening will leave the grid the same.
434 x.generator_widening_assign(y, tp);
435 }
436
437 PPL_ASSERT(OK());
438 }
439
440 void
widening_assign(const Grid & y,unsigned * tp)441 PPL::Grid::widening_assign(const Grid& y, unsigned* tp) {
442 Grid& x = *this;
443
444 // Dimension-compatibility check.
445 if (x.space_dim != y.space_dim) {
446 throw_dimension_incompatible("widening_assign(y)", "y", y);
447 }
448
449 // Assume `y' is contained in or equal to `x'.
450 PPL_EXPECT_HEAVY(copy_contains(x, y));
451
452 // If the `x' congruences are up to date and `y' congruences are up
453 // to date use the congruence widening.
454 if (x.congruences_are_up_to_date() && y.congruences_are_up_to_date()) {
455 x.congruence_widening_assign(y, tp);
456 return;
457 }
458
459 // If the `x' generators are up to date and `y' generators are up to
460 // date use the generator widening.
461 if (x.generators_are_up_to_date() && y.generators_are_up_to_date()) {
462 x.generator_widening_assign(y, tp);
463 return;
464 }
465
466 x.congruence_widening_assign(y, tp);
467 }
468
469 void
limited_extrapolation_assign(const Grid & y,const Congruence_System & cgs,unsigned * tp)470 PPL::Grid::limited_extrapolation_assign(const Grid& y,
471 const Congruence_System& cgs,
472 unsigned* tp) {
473 Grid& x = *this;
474
475 // Check dimension compatibility.
476 if (x.space_dim != y.space_dim) {
477 throw_dimension_incompatible("limited_extrapolation_assign(y, cgs)",
478 "y", y);
479 }
480
481 // `cgs' must be dimension-compatible with the two grids.
482 const dimension_type cgs_space_dim = cgs.space_dimension();
483 if (x.space_dim < cgs_space_dim) {
484 throw_dimension_incompatible("limited_extrapolation_assign(y, cgs)",
485 "cgs", cgs);
486 }
487
488 const dimension_type cgs_num_rows = cgs.num_rows();
489 // If `cgs' is empty (of rows), fall back to ordinary widening.
490 if (cgs_num_rows == 0) {
491 x.widening_assign(y, tp);
492 return;
493 }
494
495 // Assume `y' is contained in or equal to `x'.
496 PPL_EXPECT_HEAVY(copy_contains(x, y));
497
498 if (y.marked_empty()) {
499 return;
500 }
501 if (x.marked_empty()) {
502 return;
503 }
504
505 // The limited widening between two grids in a zero-dimensional
506 // space is also a grid in a zero-dimensional space.
507 if (x.space_dim == 0) {
508 return;
509 }
510
511 // Update the generators of `x': these are used to select, from the
512 // congruences in `cgs', those that must be added to the widened
513 // grid.
514 if (!x.generators_are_up_to_date() && !x.update_generators()) {
515 // `x' is empty.
516 return;
517 }
518
519 if (tp == NULL || *tp == 0) {
520 // Widening may change the grid, so add the congruences.
521 Congruence_System new_cgs;
522 // The congruences to be added need only be satisfied by all the
523 // generators of `x', as `y <= x'. Iterate upwards here, to keep
524 // the relative ordering of congruences (just for aesthetics).
525 for (dimension_type i = 0; i < cgs_num_rows; ++i) {
526 const Congruence& cg = cgs[i];
527 if (x.relation_with(cg) == Poly_Con_Relation::is_included()) {
528 new_cgs.insert(cg);
529 }
530 }
531 x.widening_assign(y, tp);
532 x.add_recycled_congruences(new_cgs);
533 }
534 else {
535 // There are tokens, so widening will leave the grid the same.
536 x.widening_assign(y, tp);
537 }
538
539 PPL_ASSERT(OK());
540 }
541