Mercurial > hg > CbC > CbC_gcc
comparison gcc/graphite-dependences.c @ 67:f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
author | nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp> |
---|---|
date | Tue, 22 Mar 2011 17:18:12 +0900 |
parents | b7f97abdc517 |
children | 04ced10e8804 |
comparison
equal
deleted
inserted
replaced
65:65488c3d617d | 67:f6334be47118 |
---|---|
20 <http://www.gnu.org/licenses/>. */ | 20 <http://www.gnu.org/licenses/>. */ |
21 | 21 |
22 #include "config.h" | 22 #include "config.h" |
23 #include "system.h" | 23 #include "system.h" |
24 #include "coretypes.h" | 24 #include "coretypes.h" |
25 #include "tm.h" | |
26 #include "ggc.h" | |
27 #include "tree.h" | |
28 #include "rtl.h" | |
29 #include "basic-block.h" | |
30 #include "diagnostic.h" | |
31 #include "tree-flow.h" | 25 #include "tree-flow.h" |
32 #include "toplev.h" | |
33 #include "tree-dump.h" | 26 #include "tree-dump.h" |
34 #include "timevar.h" | |
35 #include "cfgloop.h" | 27 #include "cfgloop.h" |
36 #include "tree-chrec.h" | 28 #include "tree-chrec.h" |
37 #include "tree-data-ref.h" | 29 #include "tree-data-ref.h" |
38 #include "tree-scalar-evolution.h" | 30 #include "tree-scalar-evolution.h" |
39 #include "tree-pass.h" | 31 #include "sese.h" |
40 #include "domwalk.h" | |
41 #include "pointer-set.h" | |
42 #include "gimple.h" | |
43 | 32 |
44 #ifdef HAVE_cloog | 33 #ifdef HAVE_cloog |
45 #include "cloog/cloog.h" | |
46 #include "ppl_c.h" | 34 #include "ppl_c.h" |
47 #include "sese.h" | |
48 #include "graphite-ppl.h" | 35 #include "graphite-ppl.h" |
49 #include "graphite.h" | |
50 #include "graphite-poly.h" | 36 #include "graphite-poly.h" |
51 #include "graphite-dependences.h" | 37 #include "graphite-dependences.h" |
52 | 38 #include "graphite-cloog-util.h" |
53 /* Returns a new polyhedral Data Dependence Relation (DDR). SOURCE is | |
54 the source data reference, SINK is the sink data reference. When | |
55 the Data Dependence Polyhedron DDP is not NULL or not empty, SOURCE | |
56 and SINK are in dependence as described by DDP. */ | |
57 | |
58 static poly_ddr_p | |
59 new_poly_ddr (poly_dr_p source, poly_dr_p sink, | |
60 ppl_Pointset_Powerset_C_Polyhedron_t ddp, | |
61 bool original_scattering_p) | |
62 { | |
63 poly_ddr_p pddr = XNEW (struct poly_ddr); | |
64 | |
65 PDDR_SOURCE (pddr) = source; | |
66 PDDR_SINK (pddr) = sink; | |
67 PDDR_DDP (pddr) = ddp; | |
68 PDDR_ORIGINAL_SCATTERING_P (pddr) = original_scattering_p; | |
69 | |
70 if (!ddp || ppl_Pointset_Powerset_C_Polyhedron_is_empty (ddp)) | |
71 PDDR_KIND (pddr) = no_dependence; | |
72 else | |
73 PDDR_KIND (pddr) = has_dependence; | |
74 | |
75 return pddr; | |
76 } | |
77 | |
78 /* Free the poly_ddr_p P. */ | |
79 | |
80 void | |
81 free_poly_ddr (void *p) | |
82 { | |
83 poly_ddr_p pddr = (poly_ddr_p) p; | |
84 ppl_delete_Pointset_Powerset_C_Polyhedron (PDDR_DDP (pddr)); | |
85 free (pddr); | |
86 } | |
87 | 39 |
88 /* Comparison function for poly_ddr hash table. */ | 40 /* Comparison function for poly_ddr hash table. */ |
89 | 41 |
90 int | 42 int |
91 eq_poly_ddr_p (const void *pddr1, const void *pddr2) | 43 eq_poly_ddr_p (const void *pddr1, const void *pddr2) |
192 if (PDDR_KIND (pddr) == has_dependence) | 144 if (PDDR_KIND (pddr) == has_dependence) |
193 { | 145 { |
194 fprintf (file, "\n dependence polyhedron (\n"); | 146 fprintf (file, "\n dependence polyhedron (\n"); |
195 print_dependence_polyhedron_layout (file, pddr); | 147 print_dependence_polyhedron_layout (file, pddr); |
196 ppl_print_powerset_matrix (file, PDDR_DDP (pddr)); | 148 ppl_print_powerset_matrix (file, PDDR_DDP (pddr)); |
149 ppl_io_fprint_Pointset_Powerset_C_Polyhedron (file, PDDR_DDP (pddr)); | |
197 fprintf (file, ")\n"); | 150 fprintf (file, ")\n"); |
198 } | 151 } |
199 | 152 |
200 fprintf (file, ")\n"); | 153 fprintf (file, ")\n"); |
201 } | 154 } |
202 | 155 |
203 /* Prints to STDERR the poly_ddr_p PDDR. */ | 156 /* Prints to STDERR the poly_ddr_p PDDR. */ |
204 | 157 |
205 void | 158 DEBUG_FUNCTION void |
206 debug_pddr (poly_ddr_p pddr) | 159 debug_pddr (poly_ddr_p pddr) |
207 { | 160 { |
208 print_pddr (stderr, pddr); | 161 print_pddr (stderr, pddr); |
209 } | 162 } |
210 | 163 |
345 } | 298 } |
346 | 299 |
347 /* Builds scheduling inequality constraints: when DIRECTION is | 300 /* Builds scheduling inequality constraints: when DIRECTION is |
348 1 builds a GE constraint, | 301 1 builds a GE constraint, |
349 0 builds an EQ constraint, | 302 0 builds an EQ constraint, |
350 -1 builds a LE constraint. */ | 303 -1 builds a LE constraint. |
304 DIM is the dimension of the scheduling space. | |
305 POS and POS + OFFSET are the dimensions that are related. */ | |
351 | 306 |
352 static ppl_Pointset_Powerset_C_Polyhedron_t | 307 static ppl_Pointset_Powerset_C_Polyhedron_t |
353 build_pairwise_scheduling (graphite_dim_t dim, | 308 build_pairwise_scheduling (graphite_dim_t dim, |
354 graphite_dim_t pos, | 309 graphite_dim_t pos, |
355 graphite_dim_t offset, | 310 graphite_dim_t offset, |
356 int direction) | 311 int direction) |
357 { | 312 { |
358 ppl_Pointset_Powerset_C_Polyhedron_t res; | 313 ppl_Pointset_Powerset_C_Polyhedron_t res; |
359 ppl_Polyhedron_t equalities; | 314 ppl_Polyhedron_t equalities; |
360 ppl_Constraint_t cstr; | 315 ppl_Constraint_t cstr; |
316 graphite_dim_t a = pos; | |
317 graphite_dim_t b = pos + offset; | |
361 | 318 |
362 ppl_new_C_Polyhedron_from_space_dimension (&equalities, dim, 0); | 319 ppl_new_C_Polyhedron_from_space_dimension (&equalities, dim, 0); |
363 | 320 |
364 switch (direction) | 321 switch (direction) |
365 { | 322 { |
366 case -1: | 323 case 1: |
367 cstr = ppl_build_relation (dim, pos, pos + offset, 1, | 324 /* Builds "a + 1 <= b. */ |
325 cstr = ppl_build_relation (dim, a, b, 1, | |
368 PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL); | 326 PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL); |
369 break; | 327 break; |
370 | 328 |
371 case 0: | 329 case 0: |
372 cstr = ppl_build_relation (dim, pos, pos + offset, 0, | 330 /* Builds "a = b. */ |
331 cstr = ppl_build_relation (dim, a, b, 0, | |
373 PPL_CONSTRAINT_TYPE_EQUAL); | 332 PPL_CONSTRAINT_TYPE_EQUAL); |
374 break; | 333 break; |
375 | 334 |
376 case 1: | 335 case -1: |
377 cstr = ppl_build_relation (dim, pos, pos + offset, -1, | 336 /* Builds "a >= b + 1. */ |
337 cstr = ppl_build_relation (dim, a, b, -1, | |
378 PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL); | 338 PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL); |
379 break; | 339 break; |
380 | 340 |
381 default: | 341 default: |
382 gcc_unreachable (); | 342 gcc_unreachable (); |
415 ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension (&res, dim, 1); | 375 ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension (&res, dim, 1); |
416 | 376 |
417 lex = build_pairwise_scheduling (dim, 0, offset, direction); | 377 lex = build_pairwise_scheduling (dim, 0, offset, direction); |
418 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (lex, bag); | 378 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (lex, bag); |
419 | 379 |
420 if (!ppl_Pointset_Powerset_C_Polyhedron_is_empty (lex)) | 380 if (!ppl_powerset_is_empty (lex)) |
421 ppl_Pointset_Powerset_C_Polyhedron_upper_bound_assign (res, lex); | 381 ppl_Pointset_Powerset_C_Polyhedron_upper_bound_assign (res, lex); |
422 | 382 |
423 ppl_delete_Pointset_Powerset_C_Polyhedron (lex); | 383 ppl_delete_Pointset_Powerset_C_Polyhedron (lex); |
424 | 384 |
425 for (i = 0; i < tdim - 1; i++) | 385 for (i = 0; i < tdim - 1; i++) |
428 | 388 |
429 sceq = build_pairwise_scheduling (dim, i, offset, 0); | 389 sceq = build_pairwise_scheduling (dim, i, offset, 0); |
430 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (bag, sceq); | 390 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (bag, sceq); |
431 ppl_delete_Pointset_Powerset_C_Polyhedron (sceq); | 391 ppl_delete_Pointset_Powerset_C_Polyhedron (sceq); |
432 | 392 |
393 if (ppl_powerset_is_empty (bag)) | |
394 break; | |
395 | |
433 lex = build_pairwise_scheduling (dim, i + 1, offset, direction); | 396 lex = build_pairwise_scheduling (dim, i + 1, offset, direction); |
434 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (lex, bag); | 397 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (lex, bag); |
435 | 398 |
436 if (!ppl_Pointset_Powerset_C_Polyhedron_is_empty (lex)) | 399 if (!ppl_powerset_is_empty (lex)) |
437 ppl_Pointset_Powerset_C_Polyhedron_upper_bound_assign (res, lex); | 400 ppl_Pointset_Powerset_C_Polyhedron_upper_bound_assign (res, lex); |
438 | 401 |
439 ppl_delete_Pointset_Powerset_C_Polyhedron (lex); | 402 ppl_delete_Pointset_Powerset_C_Polyhedron (lex); |
440 } | 403 } |
441 | 404 |
456 When DIRECTION is set to 1, compute the direct dependence from PDR1 | 419 When DIRECTION is set to 1, compute the direct dependence from PDR1 |
457 to PDR2, and when DIRECTION is -1, compute the reversed dependence | 420 to PDR2, and when DIRECTION is -1, compute the reversed dependence |
458 relation, from PDR2 to PDR1. */ | 421 relation, from PDR2 to PDR1. */ |
459 | 422 |
460 static ppl_Pointset_Powerset_C_Polyhedron_t | 423 static ppl_Pointset_Powerset_C_Polyhedron_t |
461 dependence_polyhedron_1 (poly_dr_p pdr1, poly_dr_p pdr2, | 424 dependence_polyhedron (poly_dr_p pdr1, poly_dr_p pdr2, |
462 int direction, bool original_scattering_p) | 425 int direction, bool original_scattering_p) |
463 { | 426 { |
464 poly_bb_p pbb1 = PDR_PBB (pdr1); | 427 poly_bb_p pbb1 = PDR_PBB (pdr1); |
465 poly_bb_p pbb2 = PDR_PBB (pdr2); | 428 poly_bb_p pbb2 = PDR_PBB (pdr2); |
466 scop_p scop = PBB_SCOP (pbb1); | 429 scop_p scop = PBB_SCOP (pbb1); |
467 graphite_dim_t tdim1 = original_scattering_p ? | 430 graphite_dim_t tdim1 = original_scattering_p ? |
477 graphite_dim_t dim2 = pdr_dim (pdr2); | 440 graphite_dim_t dim2 = pdr_dim (pdr2); |
478 graphite_dim_t dim = tdim1 + tdim2 + dim1 + dim2 - gdim; | 441 graphite_dim_t dim = tdim1 + tdim2 + dim1 + dim2 - gdim; |
479 ppl_Pointset_Powerset_C_Polyhedron_t res; | 442 ppl_Pointset_Powerset_C_Polyhedron_t res; |
480 ppl_Pointset_Powerset_C_Polyhedron_t idr1, idr2; | 443 ppl_Pointset_Powerset_C_Polyhedron_t idr1, idr2; |
481 ppl_Pointset_Powerset_C_Polyhedron_t sc1, sc2, dreq; | 444 ppl_Pointset_Powerset_C_Polyhedron_t sc1, sc2, dreq; |
445 ppl_Pointset_Powerset_C_Polyhedron_t lex; | |
482 | 446 |
483 gcc_assert (PBB_SCOP (pbb1) == PBB_SCOP (pbb2)); | 447 gcc_assert (PBB_SCOP (pbb1) == PBB_SCOP (pbb2)); |
484 | 448 |
485 combine_context_id_scat (&sc1, pbb1, original_scattering_p); | 449 combine_context_id_scat (&sc1, pbb1, original_scattering_p); |
486 combine_context_id_scat (&sc2, pbb2, original_scattering_p); | 450 combine_context_id_scat (&sc2, pbb2, original_scattering_p); |
510 ppl_delete_Pointset_Powerset_C_Polyhedron (sc2); | 474 ppl_delete_Pointset_Powerset_C_Polyhedron (sc2); |
511 ppl_delete_Pointset_Powerset_C_Polyhedron (idr1); | 475 ppl_delete_Pointset_Powerset_C_Polyhedron (idr1); |
512 ppl_delete_Pointset_Powerset_C_Polyhedron (idr2); | 476 ppl_delete_Pointset_Powerset_C_Polyhedron (idr2); |
513 ppl_delete_Pointset_Powerset_C_Polyhedron (dreq); | 477 ppl_delete_Pointset_Powerset_C_Polyhedron (dreq); |
514 | 478 |
515 if (!ppl_Pointset_Powerset_C_Polyhedron_is_empty (res)) | 479 if (ppl_powerset_is_empty (res)) |
516 { | 480 return NULL; |
517 ppl_Pointset_Powerset_C_Polyhedron_t lex = | 481 |
518 build_lexicographical_constraint (res, dim, MIN (tdim1, tdim2), | 482 lex = build_lexicographical_constraint (res, dim, MIN (tdim1, tdim2), |
519 tdim1 + ddim1, direction); | 483 tdim1 + ddim1, direction); |
520 ppl_delete_Pointset_Powerset_C_Polyhedron (res); | 484 ppl_delete_Pointset_Powerset_C_Polyhedron (res); |
521 res = lex; | 485 |
522 } | 486 return lex; |
523 | |
524 return res; | |
525 } | 487 } |
526 | 488 |
527 /* Build the dependence polyhedron for data references PDR1 and PDR2. | 489 /* Build the dependence polyhedron for data references PDR1 and PDR2. |
528 If possible use already cached information. | 490 If possible use already cached information. |
529 | 491 |
530 When DIRECTION is set to 1, compute the direct dependence from PDR1 | 492 When DIRECTION is set to 1, compute the direct dependence from PDR1 |
531 to PDR2, and when DIRECTION is -1, compute the reversed dependence | 493 to PDR2, and when DIRECTION is -1, compute the reversed dependence |
532 relation, from PDR2 to PDR1. */ | 494 relation, from PDR2 to PDR1. */ |
533 | 495 |
534 static poly_ddr_p | 496 static poly_ddr_p |
535 dependence_polyhedron (poly_dr_p pdr1, poly_dr_p pdr2, | 497 new_poly_ddr (poly_dr_p pdr1, poly_dr_p pdr2, |
536 int direction, bool original_scattering_p) | 498 int direction, bool original_scattering_p) |
537 { | 499 { |
538 PTR *x = NULL; | 500 PTR *x = NULL; |
539 poly_ddr_p res; | 501 poly_ddr_p res; |
540 ppl_Pointset_Powerset_C_Polyhedron_t ddp; | 502 bool may_alias; |
541 | 503 |
542 /* Return the PDDR from the cache if it already has been computed. */ | 504 /* Return the PDDR from the cache if it already has been computed. */ |
543 if (original_scattering_p) | 505 if (original_scattering_p) |
544 { | 506 { |
545 struct poly_ddr tmp; | 507 struct poly_ddr tmp; |
552 | 514 |
553 if (x && *x) | 515 if (x && *x) |
554 return (poly_ddr_p) *x; | 516 return (poly_ddr_p) *x; |
555 } | 517 } |
556 | 518 |
557 if ((pdr_read_p (pdr1) && pdr_read_p (pdr2)) | 519 res = XNEW (struct poly_ddr); |
558 || PDR_BASE_OBJECT_SET (pdr1) != PDR_BASE_OBJECT_SET (pdr2) | 520 PDDR_SOURCE (res) = pdr1; |
559 || PDR_NB_SUBSCRIPTS (pdr1) != PDR_NB_SUBSCRIPTS (pdr2) | 521 PDDR_SINK (res) = pdr2; |
560 || !poly_drs_may_alias_p (pdr1, pdr2)) | 522 PDDR_DDP (res) = NULL; |
561 ddp = NULL; | 523 PDDR_ORIGINAL_SCATTERING_P (res) = original_scattering_p; |
562 else | 524 PDDR_KIND (res) = unknown_dependence; |
563 ddp = dependence_polyhedron_1 (pdr1, pdr2, direction, | 525 |
564 original_scattering_p); | 526 may_alias = poly_drs_may_alias_p (pdr1, pdr2); |
565 | |
566 res = new_poly_ddr (pdr1, pdr2, ddp, original_scattering_p); | |
567 | 527 |
568 if (!(pdr_read_p (pdr1) && pdr_read_p (pdr2)) | 528 if (!(pdr_read_p (pdr1) && pdr_read_p (pdr2)) |
569 && PDR_BASE_OBJECT_SET (pdr1) != PDR_BASE_OBJECT_SET (pdr2) | 529 && PDR_BASE_OBJECT_SET (pdr1) != PDR_BASE_OBJECT_SET (pdr2) |
570 && poly_drs_may_alias_p (pdr1, pdr2)) | 530 && may_alias) |
571 PDDR_KIND (res) = unknown_dependence; | 531 PDDR_KIND (res) = unknown_dependence; |
532 | |
533 else if (!(pdr_read_p (pdr1) && pdr_read_p (pdr2)) | |
534 && same_pdr_p (pdr1, pdr2) | |
535 && may_alias) | |
536 { | |
537 PDDR_DDP (res) = dependence_polyhedron (pdr1, pdr2, direction, | |
538 original_scattering_p); | |
539 if (PDDR_DDP (res)) | |
540 PDDR_KIND (res) = has_dependence; | |
541 else | |
542 PDDR_KIND (res) = no_dependence; | |
543 } | |
544 else | |
545 PDDR_KIND (res) = no_dependence; | |
572 | 546 |
573 if (original_scattering_p) | 547 if (original_scattering_p) |
574 *x = res; | 548 *x = res; |
575 | 549 |
576 return res; | 550 return res; |
551 } | |
552 | |
553 /* Free the data dependence relation poly_ddr_p P. */ | |
554 | |
555 void | |
556 free_poly_ddr (void *p) | |
557 { | |
558 poly_ddr_p pddr = (poly_ddr_p) p; | |
559 ppl_delete_Pointset_Powerset_C_Polyhedron (PDDR_DDP (pddr)); | |
560 free (pddr); | |
577 } | 561 } |
578 | 562 |
579 /* Return true when the data dependence relation between the data | 563 /* Return true when the data dependence relation between the data |
580 references PDR1 belonging to PBB1 and PDR2 is part of a | 564 references PDR1 belonging to PBB1 and PDR2 is part of a |
581 reduction. */ | 565 reduction. */ |
584 reduction_dr_1 (poly_bb_p pbb1, poly_dr_p pdr1, poly_dr_p pdr2) | 568 reduction_dr_1 (poly_bb_p pbb1, poly_dr_p pdr1, poly_dr_p pdr2) |
585 { | 569 { |
586 int i; | 570 int i; |
587 poly_dr_p pdr; | 571 poly_dr_p pdr; |
588 | 572 |
589 for (i = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb1), i, pdr); i++) | 573 FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb1), i, pdr) |
590 if (PDR_TYPE (pdr) == PDR_WRITE) | 574 if (PDR_TYPE (pdr) == PDR_WRITE |
591 break; | 575 && same_pdr_p (pdr, pdr1) && same_pdr_p (pdr, pdr2)) |
592 | 576 return true; |
593 return same_pdr_p (pdr, pdr1) && same_pdr_p (pdr, pdr2); | 577 |
578 return false; | |
594 } | 579 } |
595 | 580 |
596 /* Return true when the data dependence relation between the data | 581 /* Return true when the data dependence relation between the data |
597 references PDR1 belonging to PBB1 and PDR2 belonging to PBB2 is | 582 references PDR1 belonging to PBB1 and PDR2 belonging to PBB2 is |
598 part of a reduction. */ | 583 part of a reduction. */ |
633 /* We build the reverse dependence relation for the transformed | 618 /* We build the reverse dependence relation for the transformed |
634 scattering, such that when we intersect it with the original PO, | 619 scattering, such that when we intersect it with the original PO, |
635 we get an empty intersection when the transform is legal: | 620 we get an empty intersection when the transform is legal: |
636 i.e. the transform should reverse no dependences, and so PT, the | 621 i.e. the transform should reverse no dependences, and so PT, the |
637 reversed transformed PDDR, should have no constraint from PO. */ | 622 reversed transformed PDDR, should have no constraint from PO. */ |
638 opddr = dependence_polyhedron (pdr1, pdr2, 1, true); | 623 opddr = new_poly_ddr (pdr1, pdr2, 1, true); |
639 | 624 |
640 if (PDDR_KIND (opddr) == unknown_dependence) | 625 if (PDDR_KIND (opddr) == unknown_dependence) |
641 return false; | 626 return false; |
642 | 627 |
643 /* There are no dependences between PDR1 and PDR2 in the original | 628 /* There are no dependences between PDR1 and PDR2 in the original |
644 version of the program, or after the transform, so the | 629 version of the program, or after the transform, so the |
645 transform is legal. */ | 630 transform is legal. */ |
646 if (pddr_is_empty (opddr)) | 631 if (pddr_is_empty (opddr)) |
647 return true; | 632 return true; |
648 | 633 |
649 tpddr = dependence_polyhedron (pdr1, pdr2, -1, false); | 634 tpddr = new_poly_ddr (pdr1, pdr2, -1, false); |
650 | 635 |
651 if (PDDR_KIND (tpddr) == unknown_dependence) | 636 if (PDDR_KIND (tpddr) == unknown_dependence) |
652 { | 637 { |
653 free_poly_ddr (tpddr); | 638 free_poly_ddr (tpddr); |
654 return false; | 639 return false; |
683 ttdim2); | 668 ttdim2); |
684 ppl_insert_dimensions_pointset (pt, 0, otdim1); | 669 ppl_insert_dimensions_pointset (pt, 0, otdim1); |
685 ppl_insert_dimensions_pointset (pt, otdim1 + ttdim1 + ddim1, otdim2); | 670 ppl_insert_dimensions_pointset (pt, otdim1 + ttdim1 + ddim1, otdim2); |
686 | 671 |
687 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (po_temp, pt); | 672 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (po_temp, pt); |
688 is_empty_p = ppl_Pointset_Powerset_C_Polyhedron_is_empty (po_temp); | 673 is_empty_p = ppl_powerset_is_empty (po_temp); |
689 | 674 |
690 ppl_delete_Pointset_Powerset_C_Polyhedron (po_temp); | 675 ppl_delete_Pointset_Powerset_C_Polyhedron (po_temp); |
691 free_poly_ddr (tpddr); | 676 free_poly_ddr (tpddr); |
692 | 677 |
693 if (dump_file && (dump_flags & TDF_DETAILS)) | 678 if (dump_file && (dump_flags & TDF_DETAILS)) |
721 pbb_remove_duplicate_pdrs (pbb2); | 706 pbb_remove_duplicate_pdrs (pbb2); |
722 | 707 |
723 if (reduction_ddr_p (pbb1, pbb2)) | 708 if (reduction_ddr_p (pbb1, pbb2)) |
724 return true; | 709 return true; |
725 | 710 |
726 for (i = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb1), i, pdr1); i++) | 711 FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb1), i, pdr1) |
727 for (j = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb2), j, pdr2); j++) | 712 FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb2), j, pdr2) |
728 if (!graphite_legal_transform_dr (pdr1, pdr2)) | 713 if (!graphite_legal_transform_dr (pdr1, pdr2)) |
729 return false; | 714 return false; |
730 | 715 |
731 return true; | 716 return true; |
732 } | 717 } |
740 int i, j; | 725 int i, j; |
741 poly_bb_p pbb1, pbb2; | 726 poly_bb_p pbb1, pbb2; |
742 | 727 |
743 timevar_push (TV_GRAPHITE_DATA_DEPS); | 728 timevar_push (TV_GRAPHITE_DATA_DEPS); |
744 | 729 |
745 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb1); i++) | 730 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb1) |
746 for (j = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), j, pbb2); j++) | 731 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), j, pbb2) |
747 if (!graphite_legal_transform_bb (pbb1, pbb2)) | 732 if (!graphite_legal_transform_bb (pbb1, pbb2)) |
748 { | 733 { |
749 timevar_pop (TV_GRAPHITE_DATA_DEPS); | 734 timevar_pop (TV_GRAPHITE_DATA_DEPS); |
750 return false; | 735 return false; |
751 } | 736 } |
765 ppl_Pointset_Powerset_C_Polyhedron_t eqpp; | 750 ppl_Pointset_Powerset_C_Polyhedron_t eqpp; |
766 graphite_dim_t tdim1 = pbb_nb_scattering_transform (PDR_PBB (pdr1)); | 751 graphite_dim_t tdim1 = pbb_nb_scattering_transform (PDR_PBB (pdr1)); |
767 graphite_dim_t ddim1 = pbb_dim_iter_domain (PDR_PBB (pdr1)); | 752 graphite_dim_t ddim1 = pbb_dim_iter_domain (PDR_PBB (pdr1)); |
768 ppl_dimension_type dim; | 753 ppl_dimension_type dim; |
769 bool empty_p; | 754 bool empty_p; |
770 poly_ddr_p pddr = dependence_polyhedron (pdr1, pdr2, 1, false); | 755 poly_ddr_p pddr = new_poly_ddr (pdr1, pdr2, 1, false); |
771 | 756 |
772 if (PDDR_KIND (pddr) == unknown_dependence) | 757 if (PDDR_KIND (pddr) == unknown_dependence) |
773 { | 758 { |
774 free_poly_ddr (pddr); | 759 free_poly_ddr (pddr); |
775 return true; | 760 return true; |
784 po = PDDR_DDP (pddr); | 769 po = PDDR_DDP (pddr); |
785 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (po, &dim); | 770 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (po, &dim); |
786 eqpp = build_pairwise_scheduling (dim, level, tdim1 + ddim1, 1); | 771 eqpp = build_pairwise_scheduling (dim, level, tdim1 + ddim1, 1); |
787 | 772 |
788 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (eqpp, po); | 773 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (eqpp, po); |
789 empty_p = ppl_Pointset_Powerset_C_Polyhedron_is_empty (eqpp); | 774 empty_p = ppl_powerset_is_empty (eqpp); |
790 | 775 |
791 ppl_delete_Pointset_Powerset_C_Polyhedron (eqpp); | 776 ppl_delete_Pointset_Powerset_C_Polyhedron (eqpp); |
792 free_poly_ddr (pddr); | 777 free_poly_ddr (pddr); |
793 | 778 |
794 return !empty_p; | 779 return !empty_p; |
802 int i, j; | 787 int i, j; |
803 poly_dr_p pdr1, pdr2; | 788 poly_dr_p pdr1, pdr2; |
804 | 789 |
805 timevar_push (TV_GRAPHITE_DATA_DEPS); | 790 timevar_push (TV_GRAPHITE_DATA_DEPS); |
806 | 791 |
807 for (i = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb1), i, pdr1); i++) | 792 FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb1), i, pdr1) |
808 for (j = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb2), j, pdr2); j++) | 793 FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb2), j, pdr2) |
809 if (graphite_carried_dependence_level_k (pdr1, pdr2, level)) | 794 if (graphite_carried_dependence_level_k (pdr1, pdr2, level)) |
810 { | 795 { |
811 timevar_pop (TV_GRAPHITE_DATA_DEPS); | 796 timevar_pop (TV_GRAPHITE_DATA_DEPS); |
812 return true; | 797 return true; |
813 } | 798 } |
814 | 799 |
815 timevar_pop (TV_GRAPHITE_DATA_DEPS); | 800 timevar_pop (TV_GRAPHITE_DATA_DEPS); |
816 return false; | 801 return false; |
817 } | 802 } |
818 | 803 |
819 /* Pretty print to FILE all the original data dependences of SCoP in | 804 /* When ORIG is true, pretty print to FILE all the original data |
820 DOT format. */ | 805 dependences of SCoP in DOT format, otherwise print the transformed |
806 data deps. */ | |
821 | 807 |
822 static void | 808 static void |
823 dot_original_deps_stmt_1 (FILE *file, scop_p scop) | 809 dot_deps_stmt_2 (FILE *file, scop_p scop, bool orig) |
824 { | 810 { |
825 int i, j, k, l; | 811 int i, j, k, l; |
826 poly_bb_p pbb1, pbb2; | 812 poly_bb_p pbb1, pbb2; |
827 poly_dr_p pdr1, pdr2; | 813 poly_dr_p pdr1, pdr2; |
828 | 814 |
829 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb1); i++) | 815 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb1) |
830 for (j = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), j, pbb2); j++) | 816 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), j, pbb2) |
831 { | 817 { |
832 for (k = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb1), k, pdr1); k++) | 818 FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb1), k, pdr1) |
833 for (l = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb2), l, pdr2); l++) | 819 FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb2), l, pdr2) |
834 if (!pddr_is_empty (dependence_polyhedron (pdr1, pdr2, 1, true))) | |
835 { | |
836 fprintf (file, "OS%d -> OS%d\n", | |
837 pbb_index (pbb1), pbb_index (pbb2)); | |
838 goto done; | |
839 } | |
840 done:; | |
841 } | |
842 } | |
843 | |
844 /* Pretty print to FILE all the transformed data dependences of SCoP in | |
845 DOT format. */ | |
846 | |
847 static void | |
848 dot_transformed_deps_stmt_1 (FILE *file, scop_p scop) | |
849 { | |
850 int i, j, k, l; | |
851 poly_bb_p pbb1, pbb2; | |
852 poly_dr_p pdr1, pdr2; | |
853 | |
854 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb1); i++) | |
855 for (j = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), j, pbb2); j++) | |
856 { | |
857 for (k = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb1), k, pdr1); k++) | |
858 for (l = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb2), l, pdr2); l++) | |
859 { | 820 { |
860 poly_ddr_p pddr = dependence_polyhedron (pdr1, pdr2, 1, false); | 821 poly_ddr_p pddr = new_poly_ddr (pdr1, pdr2, 1, orig); |
861 | 822 |
862 if (!pddr_is_empty (pddr)) | 823 if (!pddr_is_empty (pddr)) |
863 { | 824 { |
864 fprintf (file, "TS%d -> TS%d\n", | 825 fprintf (file, orig ? "OS%d -> OS%d\n" : "TS%d -> TS%d\n", |
865 pbb_index (pbb1), pbb_index (pbb2)); | 826 pbb_index (pbb1), pbb_index (pbb2)); |
866 | 827 |
867 free_poly_ddr (pddr); | 828 free_poly_ddr (pddr); |
868 goto done; | 829 goto done; |
869 } | 830 } |
872 } | 833 } |
873 done:; | 834 done:; |
874 } | 835 } |
875 } | 836 } |
876 | 837 |
877 | |
878 /* Pretty print to FILE all the data dependences of SCoP in DOT | 838 /* Pretty print to FILE all the data dependences of SCoP in DOT |
879 format. */ | 839 format. */ |
880 | 840 |
881 static void | 841 static void |
882 dot_deps_stmt_1 (FILE *file, scop_p scop) | 842 dot_deps_stmt_1 (FILE *file, scop_p scop) |
883 { | 843 { |
884 fputs ("digraph all {\n", file); | 844 fputs ("digraph all {\n", file); |
885 | 845 |
886 dot_original_deps_stmt_1 (file, scop); | 846 dot_deps_stmt_2 (file, scop, true); |
887 dot_transformed_deps_stmt_1 (file, scop); | 847 dot_deps_stmt_2 (file, scop, false); |
888 | 848 |
889 fputs ("}\n\n", file); | 849 fputs ("}\n\n", file); |
890 } | 850 } |
891 | 851 |
892 /* Pretty print to FILE all the original data dependences of SCoP in | 852 /* When ORIG is true, pretty print to FILE all the original data |
893 DOT format. */ | 853 dependences of SCoP in DOT format, otherwise print the transformed |
854 data deps. */ | |
894 | 855 |
895 static void | 856 static void |
896 dot_original_deps (FILE *file, scop_p scop) | 857 dot_deps_2 (FILE *file, scop_p scop, bool orig) |
897 { | 858 { |
898 int i, j, k, l; | 859 int i, j, k, l; |
899 poly_bb_p pbb1, pbb2; | 860 poly_bb_p pbb1, pbb2; |
900 poly_dr_p pdr1, pdr2; | 861 poly_dr_p pdr1, pdr2; |
901 | 862 |
902 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb1); i++) | 863 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb1) |
903 for (j = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), j, pbb2); j++) | 864 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), j, pbb2) |
904 for (k = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb1), k, pdr1); k++) | 865 FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb1), k, pdr1) |
905 for (l = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb2), l, pdr2); l++) | 866 FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb2), l, pdr2) |
906 if (!pddr_is_empty (dependence_polyhedron (pdr1, pdr2, 1, true))) | 867 { |
907 fprintf (file, "OS%d_D%d -> OS%d_D%d\n", | 868 poly_ddr_p pddr = new_poly_ddr (pdr1, pdr2, 1, orig); |
908 pbb_index (pbb1), PDR_ID (pdr1), | |
909 pbb_index (pbb2), PDR_ID (pdr2)); | |
910 } | |
911 | |
912 /* Pretty print to FILE all the transformed data dependences of SCoP in | |
913 DOT format. */ | |
914 | |
915 static void | |
916 dot_transformed_deps (FILE *file, scop_p scop) | |
917 { | |
918 int i, j, k, l; | |
919 poly_bb_p pbb1, pbb2; | |
920 poly_dr_p pdr1, pdr2; | |
921 | |
922 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb1); i++) | |
923 for (j = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), j, pbb2); j++) | |
924 for (k = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb1), k, pdr1); k++) | |
925 for (l = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb2), l, pdr2); l++) | |
926 { | |
927 poly_ddr_p pddr = dependence_polyhedron (pdr1, pdr2, 1, false); | |
928 | 869 |
929 if (!pddr_is_empty (pddr)) | 870 if (!pddr_is_empty (pddr)) |
930 fprintf (file, "TS%d_D%d -> TS%d_D%d\n", | 871 fprintf (file, orig |
872 ? "OS%d_D%d -> OS%d_D%d\n" : "TS%d_D%d -> TS%d_D%d\n", | |
931 pbb_index (pbb1), PDR_ID (pdr1), | 873 pbb_index (pbb1), PDR_ID (pdr1), |
932 pbb_index (pbb2), PDR_ID (pdr2)); | 874 pbb_index (pbb2), PDR_ID (pdr2)); |
933 | 875 |
934 free_poly_ddr (pddr); | 876 free_poly_ddr (pddr); |
935 } | 877 } |
941 static void | 883 static void |
942 dot_deps_1 (FILE *file, scop_p scop) | 884 dot_deps_1 (FILE *file, scop_p scop) |
943 { | 885 { |
944 fputs ("digraph all {\n", file); | 886 fputs ("digraph all {\n", file); |
945 | 887 |
946 dot_original_deps (file, scop); | 888 dot_deps_2 (file, scop, true); |
947 dot_transformed_deps (file, scop); | 889 dot_deps_2 (file, scop, false); |
948 | 890 |
949 fputs ("}\n\n", file); | 891 fputs ("}\n\n", file); |
950 } | 892 } |
951 | 893 |
952 /* Display all the data dependences in SCoP using dotty. */ | 894 /* Display all the data dependences in SCoP using dotty. */ |
953 | 895 |
954 void | 896 DEBUG_FUNCTION void |
955 dot_deps (scop_p scop) | 897 dot_deps (scop_p scop) |
956 { | 898 { |
957 /* When debugging, enable the following code. This cannot be used | 899 /* When debugging, enable the following code. This cannot be used |
958 in production compilers because it calls "system". */ | 900 in production compilers because it calls "system". */ |
959 #if 0 | 901 #if 0 |
960 int x; | |
961 FILE *stream = fopen ("/tmp/scopdeps.dot", "w"); | 902 FILE *stream = fopen ("/tmp/scopdeps.dot", "w"); |
962 gcc_assert (stream); | 903 gcc_assert (stream); |
963 | 904 |
964 dot_deps_1 (stream, scop); | 905 dot_deps_1 (stream, scop); |
965 fclose (stream); | 906 fclose (stream); |
966 | 907 |
967 x = system ("dotty /tmp/scopdeps.dot"); | 908 system ("dotty /tmp/scopdeps.dot &"); |
968 #else | 909 #else |
969 dot_deps_1 (stderr, scop); | 910 dot_deps_1 (stderr, scop); |
970 #endif | 911 #endif |
971 } | 912 } |
972 | 913 |
973 /* Display all the statement dependences in SCoP using dotty. */ | 914 /* Display all the statement dependences in SCoP using dotty. */ |
974 | 915 |
975 void | 916 DEBUG_FUNCTION void |
976 dot_deps_stmt (scop_p scop) | 917 dot_deps_stmt (scop_p scop) |
977 { | 918 { |
978 /* When debugging, enable the following code. This cannot be used | 919 /* When debugging, enable the following code. This cannot be used |
979 in production compilers because it calls "system". */ | 920 in production compilers because it calls "system". */ |
980 #if 0 | 921 #if 0 |
981 int x; | |
982 FILE *stream = fopen ("/tmp/scopdeps.dot", "w"); | 922 FILE *stream = fopen ("/tmp/scopdeps.dot", "w"); |
983 gcc_assert (stream); | 923 gcc_assert (stream); |
984 | 924 |
985 dot_deps_stmt_1 (stream, scop); | 925 dot_deps_stmt_1 (stream, scop); |
986 fclose (stream); | 926 fclose (stream); |
987 | 927 |
988 x = system ("dotty /tmp/scopdeps.dot"); | 928 system ("dotty /tmp/scopdeps.dot &"); |
989 #else | 929 #else |
990 dot_deps_stmt_1 (stderr, scop); | 930 dot_deps_stmt_1 (stderr, scop); |
991 #endif | 931 #endif |
992 } | 932 } |
993 | 933 |