Mercurial > hg > CbC > CbC_gcc

comparison gcc/graphite-ppl.c @ 63:b7f97abdc517 gcc-4.6-20100522

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
update gcc from gcc-4.5.0 to gcc-4.6
author ryoma <e075725@ie.u-ryukyu.ac.jp>
date Mon, 24 May 2010 12:47:05 +0900
parents 77e2b8dfacca
children f6334be47118
comparison
equal deleted inserted replaced
56:3c8a44c06a95 63:b7f97abdc517
1 /* Gimple Represented as Polyhedra. 1 /* Gimple Represented as Polyhedra.
2 Copyright (C) 2009 Free Software Foundation, Inc. 2 Copyright (C) 2009, 2010 Free Software Foundation, Inc.
3 Contributed by Sebastian Pop <sebastian.pop@amd.com> 3 Contributed by Sebastian Pop <sebastian.pop@amd.com>
4 and Tobias Grosser <grosser@fim.uni-passau.de> 4 and Tobias Grosser <grosser@fim.uni-passau.de>
5 5
6 This file is part of GCC. 6 This file is part of GCC.
7 7
24 #include "coretypes.h" 24 #include "coretypes.h"
25 #include "tm.h" 25 #include "tm.h"
26 #include "ggc.h" 26 #include "ggc.h"
27 27
28 #ifdef HAVE_cloog 28 #ifdef HAVE_cloog
29
29 #include "ppl_c.h" 30 #include "ppl_c.h"
30 #include "cloog/cloog.h" 31 #include "cloog/cloog.h"
31 #include "graphite-ppl.h" 32 #include "graphite-ppl.h"
32 33
33 /* Translates row ROW of the CloogMatrix MATRIX to a PPL Constraint. */ 34 /* Translates row ROW of the CloogMatrix MATRIX to a PPL Constraint. */
53 ppl_assign_Coefficient_from_mpz_t (coef, 54 ppl_assign_Coefficient_from_mpz_t (coef,
54 matrix->p[row][matrix->NbColumns - 1]); 55 matrix->p[row][matrix->NbColumns - 1]);
55 ppl_Linear_Expression_add_to_inhomogeneous (expr, coef); 56 ppl_Linear_Expression_add_to_inhomogeneous (expr, coef);
56 ppl_delete_Coefficient (coef); 57 ppl_delete_Coefficient (coef);
57 58
58 if (value_zero_p (matrix->p[row][0])) 59 if (mpz_sgn (matrix->p[row][0]))
59 ppl_new_Constraint (&cstr, expr, PPL_CONSTRAINT_TYPE_EQUAL); 60 ppl_new_Constraint (&cstr, expr, PPL_CONSTRAINT_TYPE_EQUAL);
60 else 61 else
61 ppl_new_Constraint (&cstr, expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL); 62 ppl_new_Constraint (&cstr, expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
62 63
63 ppl_delete_Linear_Expression (expr); 64 ppl_delete_Linear_Expression (expr);
120 { 121 {
121 int k; 122 int k;
122 123
123 /* Do not oppose the first column: it is the eq/ineq one. */ 124 /* Do not oppose the first column: it is the eq/ineq one. */
124 for (k = 1; k < m->NbColumns; k++) 125 for (k = 1; k < m->NbColumns; k++)
125 value_oppose (m->p[row][k], m->p[row][k]); 126 mpz_neg (m->p[row][k], m->p[row][k]);
126 } 127 }
127 128
128 /* Inserts constraint CSTR at row ROW of matrix M. */ 129 /* Inserts constraint CSTR at row ROW of matrix M. */
129 130
130 void 131 void
142 ppl_Constraint_coefficient (cstr, i, c); 143 ppl_Constraint_coefficient (cstr, i, c);
143 ppl_Coefficient_to_mpz_t (c, m->p[row][i + 1]); 144 ppl_Coefficient_to_mpz_t (c, m->p[row][i + 1]);
144 } 145 }
145 146
146 for (i = dim; i < nb_cols - 1; i++) 147 for (i = dim; i < nb_cols - 1; i++)
147 value_set_si (m->p[row][i + 1], 0); 148 mpz_set_si (m->p[row][i + 1], 0);
148 149
149 ppl_Constraint_inhomogeneous_term (cstr, c); 150 ppl_Constraint_inhomogeneous_term (cstr, c);
150 ppl_Coefficient_to_mpz_t (c, m->p[row][nb_cols - 1]); 151 ppl_Coefficient_to_mpz_t (c, m->p[row][nb_cols - 1]);
151 value_set_si (m->p[row][0], 1); 152 mpz_set_si (m->p[row][0], 1);
152 153
153 switch (ppl_Constraint_type (cstr)) 154 switch (ppl_Constraint_type (cstr))
154 { 155 {
155 case PPL_CONSTRAINT_TYPE_LESS_THAN: 156 case PPL_CONSTRAINT_TYPE_LESS_THAN:
156 oppose_constraint (m, row); 157 oppose_constraint (m, row);
157 case PPL_CONSTRAINT_TYPE_GREATER_THAN: 158 case PPL_CONSTRAINT_TYPE_GREATER_THAN:
158 value_sub_int (m->p[row][nb_cols - 1], 159 mpz_sub_ui (m->p[row][nb_cols - 1],
159 m->p[row][nb_cols - 1], 1); 160 m->p[row][nb_cols - 1], 1);
160 break; 161 break;
161 162
162 case PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL: 163 case PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL:
163 oppose_constraint (m, row); 164 oppose_constraint (m, row);
164 case PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL: 165 case PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL:
165 break; 166 break;
166 167
167 case PPL_CONSTRAINT_TYPE_EQUAL: 168 case PPL_CONSTRAINT_TYPE_EQUAL:
168 value_set_si (m->p[row][0], 0); 169 mpz_set_si (m->p[row][0], 0);
169 break; 170 break;
170 171
171 default: 172 default:
172 /* Not yet implemented. */ 173 /* Not yet implemented. */
173 gcc_unreachable(); 174 gcc_unreachable();
273 } 274 }
274 275
275 /* Set the inhomogeneous term of E to X. */ 276 /* Set the inhomogeneous term of E to X. */
276 277
277 void 278 void
278 ppl_set_inhomogeneous_gmp (ppl_Linear_Expression_t e, Value x) 279 ppl_set_inhomogeneous_gmp (ppl_Linear_Expression_t e, mpz_t x)
279 { 280 {
280 Value v0, v1; 281 mpz_t v0, v1;
281 ppl_Coefficient_t c; 282 ppl_Coefficient_t c;
282 283
283 value_init (v0); 284 mpz_init (v0);
284 value_init (v1); 285 mpz_init (v1);
285 ppl_new_Coefficient (&c); 286 ppl_new_Coefficient (&c);
286 287
287 ppl_Linear_Expression_inhomogeneous_term (e, c); 288 ppl_Linear_Expression_inhomogeneous_term (e, c);
288 ppl_Coefficient_to_mpz_t (c, v1); 289 ppl_Coefficient_to_mpz_t (c, v1);
289 value_oppose (v1, v1); 290 mpz_neg (v1, v1);
290 value_assign (v0, x); 291 mpz_set (v0, x);
291 value_addto (v0, v0, v1); 292 mpz_add (v0, v0, v1);
292 ppl_assign_Coefficient_from_mpz_t (c, v0); 293 ppl_assign_Coefficient_from_mpz_t (c, v0);
293 ppl_Linear_Expression_add_to_inhomogeneous (e, c); 294 ppl_Linear_Expression_add_to_inhomogeneous (e, c);
294 295
295 value_clear (v0); 296 mpz_clear (v0);
296 value_clear (v1); 297 mpz_clear (v1);
297 ppl_delete_Coefficient (c); 298 ppl_delete_Coefficient (c);
298 } 299 }
299 300
300 /* Set E[I] to X. */ 301 /* Set E[I] to X. */
301 302
302 void 303 void
303 ppl_set_coef_gmp (ppl_Linear_Expression_t e, ppl_dimension_type i, Value x) 304 ppl_set_coef_gmp (ppl_Linear_Expression_t e, ppl_dimension_type i, mpz_t x)
304 { 305 {
305 Value v0, v1; 306 mpz_t v0, v1;
306 ppl_Coefficient_t c; 307 ppl_Coefficient_t c;
307 308
308 value_init (v0); 309 mpz_init (v0);
309 value_init (v1); 310 mpz_init (v1);
310 ppl_new_Coefficient (&c); 311 ppl_new_Coefficient (&c);
311 312
312 ppl_Linear_Expression_coefficient (e, i, c); 313 ppl_Linear_Expression_coefficient (e, i, c);
313 ppl_Coefficient_to_mpz_t (c, v1); 314 ppl_Coefficient_to_mpz_t (c, v1);
314 value_oppose (v1, v1); 315 mpz_neg (v1, v1);
315 value_assign (v0, x); 316 mpz_set (v0, x);
316 value_addto (v0, v0, v1); 317 mpz_add (v0, v0, v1);
317 ppl_assign_Coefficient_from_mpz_t (c, v0); 318 ppl_assign_Coefficient_from_mpz_t (c, v0);
318 ppl_Linear_Expression_add_to_coefficient (e, i, c); 319 ppl_Linear_Expression_add_to_coefficient (e, i, c);
319 320
320 value_clear (v0); 321 mpz_clear (v0);
321 value_clear (v1); 322 mpz_clear (v1);
322 ppl_delete_Coefficient (c); 323 ppl_delete_Coefficient (c);
323 } 324 }
324 325
325 /* Insert after X NB_NEW_DIMS empty dimensions into PH. 326 /* Insert after X NB_NEW_DIMS empty dimensions into PH.
326 327
419 ppl_Linear_Expression_t expr; 420 ppl_Linear_Expression_t expr;
420 int v; 421 int v;
421 ppl_dimension_type dim; 422 ppl_dimension_type dim;
422 ppl_Polyhedron_t res; 423 ppl_Polyhedron_t res;
423 ppl_Coefficient_t c; 424 ppl_Coefficient_t c;
424 Value val; 425 mpz_t val;
425 426
426 value_init (val); 427 mpz_init (val);
427 ppl_new_Coefficient (&c); 428 ppl_new_Coefficient (&c);
428 429
429 ppl_Polyhedron_space_dimension (ph, &dim); 430 ppl_Polyhedron_space_dimension (ph, &dim);
430 ppl_Polyhedron_get_constraints (ph, &pcs); 431 ppl_Polyhedron_get_constraints (ph, &pcs);
431 432
453 ppl_Constraint_System_const_iterator_dereference (cit, &cstr); 454 ppl_Constraint_System_const_iterator_dereference (cit, &cstr);
454 ppl_new_Linear_Expression_from_Constraint (&expr, cstr); 455 ppl_new_Linear_Expression_from_Constraint (&expr, cstr);
455 ppl_Linear_Expression_coefficient (expr, loop, c); 456 ppl_Linear_Expression_coefficient (expr, loop, c);
456 ppl_delete_Linear_Expression (expr); 457 ppl_delete_Linear_Expression (expr);
457 ppl_Coefficient_to_mpz_t (c, val); 458 ppl_Coefficient_to_mpz_t (c, val);
458 v = value_get_si (val); 459 v = mpz_get_si (val);
459 460
460 if (0 < v || v < 0) 461 if (0 < v || v < 0)
461 ppl_Polyhedron_add_constraint (tmp, cstr); 462 ppl_Polyhedron_add_constraint (tmp, cstr);
462 } 463 }
463 ppl_delete_Constraint_System_const_iterator (cit); 464 ppl_delete_Constraint_System_const_iterator (cit);
497 ppl_delete_Linear_Expression (expr); 498 ppl_delete_Linear_Expression (expr);
498 ppl_Polyhedron_add_constraint (res, new_cstr); 499 ppl_Polyhedron_add_constraint (res, new_cstr);
499 ppl_delete_Constraint (new_cstr); 500 ppl_delete_Constraint (new_cstr);
500 } 501 }
501 502
502 value_clear (val); 503 mpz_clear (val);
503 ppl_delete_Coefficient (c); 504 ppl_delete_Coefficient (c);
504 return res; 505 return res;
505 } 506 }
506 507
507 /* Lexicographically compares two linear expressions A and B and 508 /* Lexicographically compares two linear expressions A and B and
513 { 514 {
514 ppl_dimension_type min_length, length1, length2; 515 ppl_dimension_type min_length, length1, length2;
515 ppl_dimension_type i; 516 ppl_dimension_type i;
516 ppl_Coefficient_t c; 517 ppl_Coefficient_t c;
517 int res; 518 int res;
518 Value va, vb; 519 mpz_t va, vb;
519 520
520 ppl_Linear_Expression_space_dimension (a, &length1); 521 ppl_Linear_Expression_space_dimension (a, &length1);
521 ppl_Linear_Expression_space_dimension (b, &length2); 522 ppl_Linear_Expression_space_dimension (b, &length2);
522 ppl_new_Coefficient (&c); 523 ppl_new_Coefficient (&c);
523 value_init (va); 524 mpz_init (va);
524 value_init (vb); 525 mpz_init (vb);
525 526
526 if (length1 < length2) 527 if (length1 < length2)
527 min_length = length1; 528 min_length = length1;
528 else 529 else
529 min_length = length2; 530 min_length = length2;
532 { 533 {
533 ppl_Linear_Expression_coefficient (a, i, c); 534 ppl_Linear_Expression_coefficient (a, i, c);
534 ppl_Coefficient_to_mpz_t (c, va); 535 ppl_Coefficient_to_mpz_t (c, va);
535 ppl_Linear_Expression_coefficient (b, i, c); 536 ppl_Linear_Expression_coefficient (b, i, c);
536 ppl_Coefficient_to_mpz_t (c, vb); 537 ppl_Coefficient_to_mpz_t (c, vb);
537 res = value_compare (va, vb); 538 res = mpz_cmp (va, vb);
538 539
539 if (res == 0) 540 if (res == 0)
540 continue; 541 continue;
541 542
542 value_clear (va); 543 mpz_clear (va);
543 value_clear (vb); 544 mpz_clear (vb);
544 ppl_delete_Coefficient (c); 545 ppl_delete_Coefficient (c);
545 return res; 546 return res;
546 } 547 }
547 548
548 value_clear (va); 549 mpz_clear (va);
549 value_clear (vb); 550 mpz_clear (vb);
550 ppl_delete_Coefficient (c); 551 ppl_delete_Coefficient (c);
551 return length1 - length2; 552 return length1 - length2;
552 } 553 }
553 554
554 /* Print to FILE the polyhedron PH under its PolyLib matrix form. */ 555 /* Print to FILE the polyhedron PH under its PolyLib matrix form. */
589 590
590 void 591 void
591 ppl_print_powerset_matrix (FILE *file, 592 ppl_print_powerset_matrix (FILE *file,
592 ppl_Pointset_Powerset_C_Polyhedron_t ps) 593 ppl_Pointset_Powerset_C_Polyhedron_t ps)
593 { 594 {
595 size_t nb_disjuncts;
594 ppl_Pointset_Powerset_C_Polyhedron_iterator_t it, end; 596 ppl_Pointset_Powerset_C_Polyhedron_iterator_t it, end;
595 597
596 ppl_new_Pointset_Powerset_C_Polyhedron_iterator (&it); 598 ppl_new_Pointset_Powerset_C_Polyhedron_iterator (&it);
597 ppl_new_Pointset_Powerset_C_Polyhedron_iterator (&end); 599 ppl_new_Pointset_Powerset_C_Polyhedron_iterator (&end);
600
601 ppl_Pointset_Powerset_C_Polyhedron_size (ps, &nb_disjuncts);
602 fprintf (file, "%d\n", (int) nb_disjuncts);
598 603
599 for (ppl_Pointset_Powerset_C_Polyhedron_iterator_begin (ps, it), 604 for (ppl_Pointset_Powerset_C_Polyhedron_iterator_begin (ps, it),
600 ppl_Pointset_Powerset_C_Polyhedron_iterator_end (ps, end); 605 ppl_Pointset_Powerset_C_Polyhedron_iterator_end (ps, end);
601 !ppl_Pointset_Powerset_C_Polyhedron_iterator_equal_test (it, end); 606 !ppl_Pointset_Powerset_C_Polyhedron_iterator_equal_test (it, end);
602 ppl_Pointset_Powerset_C_Polyhedron_iterator_increment (it)) 607 ppl_Pointset_Powerset_C_Polyhedron_iterator_increment (it))
641 /* Return in RES the maximum of the linear expression LE on the 646 /* Return in RES the maximum of the linear expression LE on the
642 pointset powerset of polyhedra PS. */ 647 pointset powerset of polyhedra PS. */
643 648
644 void 649 void
645 ppl_max_for_le_pointset (ppl_Pointset_Powerset_C_Polyhedron_t ps, 650 ppl_max_for_le_pointset (ppl_Pointset_Powerset_C_Polyhedron_t ps,
646 ppl_Linear_Expression_t le, Value res) 651 ppl_Linear_Expression_t le, mpz_t res)
647 { 652 {
648 ppl_Coefficient_t num, denom; 653 ppl_Coefficient_t num, denom;
649 Value dv, nv; 654 mpz_t dv, nv;
650 int maximum, err; 655 int maximum, err;
651 656
652 value_init (nv); 657 mpz_init (nv);
653 value_init (dv); 658 mpz_init (dv);
654 ppl_new_Coefficient (&num); 659 ppl_new_Coefficient (&num);
655 ppl_new_Coefficient (&denom); 660 ppl_new_Coefficient (&denom);
656 err = ppl_Pointset_Powerset_C_Polyhedron_maximize (ps, le, num, denom, &maximum); 661 err = ppl_Pointset_Powerset_C_Polyhedron_maximize (ps, le, num, denom, &maximum);
657 662
658 if (err > 0) 663 if (err > 0)
659 { 664 {
660 ppl_Coefficient_to_mpz_t (num, nv); 665 ppl_Coefficient_to_mpz_t (num, nv);
661 ppl_Coefficient_to_mpz_t (denom, dv); 666 ppl_Coefficient_to_mpz_t (denom, dv);
662 gcc_assert (value_notzero_p (dv)); 667 gcc_assert (value_notzero_p (dv));
663 value_division (res, nv, dv); 668 mpz_tdiv_q (res, nv, dv);
664 } 669 }
665 670
666 value_clear (nv); 671 mpz_clear (nv);
667 value_clear (dv); 672 mpz_clear (dv);
668 ppl_delete_Coefficient (num); 673 ppl_delete_Coefficient (num);
669 ppl_delete_Coefficient (denom); 674 ppl_delete_Coefficient (denom);
670 } 675 }
671 676
672 /* Return in RES the maximum of the linear expression LE on the 677 /* Return in RES the maximum of the linear expression LE on the
673 polyhedron POL. */ 678 polyhedron POL. */
674 679
675 void 680 void
676 ppl_min_for_le_polyhedron (ppl_Polyhedron_t pol, 681 ppl_min_for_le_pointset (ppl_Pointset_Powerset_C_Polyhedron_t ps,
677 ppl_Linear_Expression_t le, Value res) 682 ppl_Linear_Expression_t le, mpz_t res)
678 { 683 {
679 ppl_Coefficient_t num, denom; 684 ppl_Coefficient_t num, denom;
680 Value dv, nv; 685 mpz_t dv, nv;
681 int maximum, err; 686 int minimum, err;
682 687
683 value_init (nv); 688 mpz_init (nv);
684 value_init (dv); 689 mpz_init (dv);
685 ppl_new_Coefficient (&num); 690 ppl_new_Coefficient (&num);
686 ppl_new_Coefficient (&denom); 691 ppl_new_Coefficient (&denom);
687 err = ppl_Polyhedron_minimize (pol, le, num, denom, &maximum); 692 err = ppl_Pointset_Powerset_C_Polyhedron_minimize (ps, le, num, denom, &minimum);
688 693
689 if (err > 0) 694 if (err > 0)
690 { 695 {
691 ppl_Coefficient_to_mpz_t (num, nv); 696 ppl_Coefficient_to_mpz_t (num, nv);
692 ppl_Coefficient_to_mpz_t (denom, dv); 697 ppl_Coefficient_to_mpz_t (denom, dv);
693 gcc_assert (value_notzero_p (dv)); 698 gcc_assert (value_notzero_p (dv));
694 value_division (res, nv, dv); 699 mpz_tdiv_q (res, nv, dv);
695 } 700 }
696 701
697 value_clear (nv); 702 mpz_clear (nv);
698 value_clear (dv); 703 mpz_clear (dv);
699 ppl_delete_Coefficient (num); 704 ppl_delete_Coefficient (num);
700 ppl_delete_Coefficient (denom); 705 ppl_delete_Coefficient (denom);
701 } 706 }
702 707
708 /* Builds a constraint in dimension DIM relating dimensions POS1 to
709 POS2 as "POS1 - POS2 + C CSTR_TYPE 0" */
710
711 ppl_Constraint_t
712 ppl_build_relation (int dim, int pos1, int pos2, int c,
713 enum ppl_enum_Constraint_Type cstr_type)
714 {
715 ppl_Linear_Expression_t expr;
716 ppl_Constraint_t cstr;
717 ppl_Coefficient_t coef;
718 mpz_t v, v_op, v_c;
719
720 mpz_init (v);
721 mpz_init (v_op);
722 mpz_init (v_c);
723
724 mpz_set_si (v, 1);
725 mpz_set_si (v_op, -1);
726 mpz_set_si (v_c, c);
727
728 ppl_new_Coefficient (&coef);
729 ppl_new_Linear_Expression_with_dimension (&expr, dim);
730
731 ppl_assign_Coefficient_from_mpz_t (coef, v);
732 ppl_Linear_Expression_add_to_coefficient (expr, pos1, coef);
733 ppl_assign_Coefficient_from_mpz_t (coef, v_op);
734 ppl_Linear_Expression_add_to_coefficient (expr, pos2, coef);
735 ppl_assign_Coefficient_from_mpz_t (coef, v_c);
736 ppl_Linear_Expression_add_to_inhomogeneous (expr, coef);
737
738 ppl_new_Constraint (&cstr, expr, cstr_type);
739
740 ppl_delete_Linear_Expression (expr);
741 ppl_delete_Coefficient (coef);
742 mpz_clear (v);
743 mpz_clear (v_op);
744 mpz_clear (v_c);
745
746 return cstr;
747 }
703 748
704 #endif 749 #endif