LCOV - code coverage report
Current view: top level - gcc - graphite-dependences.c (source / functions) Hit Total Coverage
Test: gcc.info Lines: 150 161 93.2 %
Date: 2020-04-04 11:58:09 Functions: 10 10 100.0 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 0 -

           Branch data     Line data    Source code
       1                 :            : /* Data dependence analysis for Graphite.
       2                 :            :    Copyright (C) 2009-2020 Free Software Foundation, Inc.
       3                 :            :    Contributed by Sebastian Pop <sebastian.pop@amd.com> and
       4                 :            :    Konrad Trifunovic <konrad.trifunovic@inria.fr>.
       5                 :            : 
       6                 :            : This file is part of GCC.
       7                 :            : 
       8                 :            : GCC is free software; you can redistribute it and/or modify
       9                 :            : it under the terms of the GNU General Public License as published by
      10                 :            : the Free Software Foundation; either version 3, or (at your option)
      11                 :            : any later version.
      12                 :            : 
      13                 :            : GCC is distributed in the hope that it will be useful,
      14                 :            : but WITHOUT ANY WARRANTY; without even the implied warranty of
      15                 :            : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      16                 :            : GNU General Public License for more details.
      17                 :            : 
      18                 :            : You should have received a copy of the GNU General Public License
      19                 :            : along with GCC; see the file COPYING3.  If not see
      20                 :            : <http://www.gnu.org/licenses/>.  */
      21                 :            : 
      22                 :            : #define USES_ISL
      23                 :            : 
      24                 :            : #include "config.h"
      25                 :            : 
      26                 :            : #ifdef HAVE_isl
      27                 :            : 
      28                 :            : #include "system.h"
      29                 :            : #include "coretypes.h"
      30                 :            : #include "backend.h"
      31                 :            : #include "cfghooks.h"
      32                 :            : #include "tree.h"
      33                 :            : #include "gimple.h"
      34                 :            : #include "fold-const.h"
      35                 :            : #include "gimple-iterator.h"
      36                 :            : #include "tree-ssa-loop.h"
      37                 :            : #include "tree-pass.h"
      38                 :            : #include "cfgloop.h"
      39                 :            : #include "tree-data-ref.h"
      40                 :            : #include "graphite.h"
      41                 :            : 
      42                 :            : /* Add the constraints from the set S to the domain of MAP.  */
      43                 :            : 
      44                 :            : static isl_map *
      45                 :       1370 : constrain_domain (isl_map *map, isl_set *s)
      46                 :            : {
      47                 :       1370 :   isl_space *d = isl_map_get_space (map);
      48                 :       1370 :   isl_id *id = isl_space_get_tuple_id (d, isl_dim_in);
      49                 :            : 
      50                 :       1370 :   s = isl_set_set_tuple_id (s, id);
      51                 :       1370 :   isl_space_free (d);
      52                 :       1370 :   return isl_map_coalesce (isl_map_intersect_domain (map, s));
      53                 :            : }
      54                 :            : 
      55                 :            : /* Constrain pdr->accesses with pdr->subscript_sizes and pbb->domain.  */
      56                 :            : 
      57                 :            : static isl_map *
      58                 :       1370 : add_pdr_constraints (poly_dr_p pdr, poly_bb_p pbb)
      59                 :            : {
      60                 :       1370 :   isl_map *x = isl_map_intersect_range (isl_map_copy (pdr->accesses),
      61                 :            :                                         isl_set_copy (pdr->subscript_sizes));
      62                 :       1370 :   x = isl_map_coalesce (x);
      63                 :       1370 :   return constrain_domain (x, isl_set_copy (pbb->domain));
      64                 :            : }
      65                 :            : 
      66                 :            : /* Returns an isl description of all memory operations in SCOP.  The memory
      67                 :            :    reads are returned in READS and writes in MUST_WRITES and MAY_WRITES.  */
      68                 :            : 
      69                 :            : static void
      70                 :        126 : scop_get_reads_and_writes (scop_p scop, isl_union_map *&reads,
      71                 :            :                            isl_union_map *&must_writes,
      72                 :            :                            isl_union_map *&may_writes)
      73                 :            : {
      74                 :        126 :   int i, j;
      75                 :        126 :   poly_bb_p pbb;
      76                 :        126 :   poly_dr_p pdr;
      77                 :            : 
      78                 :        916 :   FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
      79                 :            :     {
      80                 :       2160 :       FOR_EACH_VEC_ELT (PBB_DRS (pbb), j, pdr) {
      81                 :       1370 :         if (pdr_read_p (pdr))
      82                 :            :           {
      83                 :        629 :             if (dump_file)
      84                 :            :               {
      85                 :        326 :                 fprintf (dump_file, "Adding read to depedence graph: ");
      86                 :        326 :                 print_pdr (dump_file, pdr);
      87                 :            :               }
      88                 :        629 :             isl_union_map *um
      89                 :        629 :               = isl_union_map_from_map (add_pdr_constraints (pdr, pbb));
      90                 :        629 :             reads = isl_union_map_union (reads, um);
      91                 :        629 :             if (dump_file)
      92                 :            :               {
      93                 :        326 :                 fprintf (dump_file, "Reads depedence graph: ");
      94                 :        326 :                 print_isl_union_map (dump_file, reads);
      95                 :            :               }
      96                 :            :           }
      97                 :        741 :         else if (pdr_write_p (pdr))
      98                 :            :           {
      99                 :        741 :             if (dump_file)
     100                 :            :               {
     101                 :        400 :                 fprintf (dump_file, "Adding must write to depedence graph: ");
     102                 :        400 :                 print_pdr (dump_file, pdr);
     103                 :            :               }
     104                 :        741 :             isl_union_map *um
     105                 :        741 :               = isl_union_map_from_map (add_pdr_constraints (pdr, pbb));
     106                 :        741 :             must_writes = isl_union_map_union (must_writes, um);
     107                 :        741 :             if (dump_file)
     108                 :            :               {
     109                 :        400 :                 fprintf (dump_file, "Must writes depedence graph: ");
     110                 :        400 :                 print_isl_union_map (dump_file, must_writes);
     111                 :            :               }
     112                 :            :           }
     113                 :          0 :         else if (pdr_may_write_p (pdr))
     114                 :            :           {
     115                 :          0 :             if (dump_file)
     116                 :            :               {
     117                 :          0 :                 fprintf (dump_file, "Adding may write to depedence graph: ");
     118                 :          0 :                 print_pdr (dump_file, pdr);
     119                 :            :               }
     120                 :          0 :             isl_union_map *um
     121                 :          0 :               = isl_union_map_from_map (add_pdr_constraints (pdr, pbb));
     122                 :          0 :             may_writes = isl_union_map_union (may_writes, um);
     123                 :          0 :             if (dump_file)
     124                 :            :               {
     125                 :          0 :                 fprintf (dump_file, "May writes depedence graph: ");
     126                 :          0 :                 print_isl_union_map (dump_file, may_writes);
     127                 :            :               }
     128                 :            :           }
     129                 :            :       }
     130                 :            :     }
     131                 :        126 : }
     132                 :            : 
     133                 :            : /* Helper function used on each MAP of a isl_union_map.  Computes the
     134                 :            :    maximal output dimension.  */
     135                 :            : 
     136                 :            : static isl_stat
     137                 :         54 : max_number_of_out_dimensions (__isl_take isl_map *map, void *user)
     138                 :            : {
     139                 :         54 :   int global_max = *((int *) user);
     140                 :         54 :   isl_space *space = isl_map_get_space (map);
     141                 :         54 :   int nb_out = isl_space_dim (space, isl_dim_out);
     142                 :            : 
     143                 :         54 :   if (global_max < nb_out)
     144                 :         43 :     *((int *) user) = nb_out;
     145                 :            : 
     146                 :         54 :   isl_map_free (map);
     147                 :         54 :   isl_space_free (space);
     148                 :         54 :   return isl_stat_ok;
     149                 :            : }
     150                 :            : 
     151                 :            : /* Extends the output dimension of MAP to MAX dimensions.  */
     152                 :            : 
     153                 :            : static __isl_give isl_map *
     154                 :         54 : extend_map (__isl_take isl_map *map, int max)
     155                 :            : {
     156                 :         54 :   isl_space *space = isl_map_get_space (map);
     157                 :         54 :   int n = isl_space_dim (space, isl_dim_out);
     158                 :            : 
     159                 :         54 :   isl_space_free (space);
     160                 :         54 :   return isl_map_add_dims (map, isl_dim_out, max - n);
     161                 :            : }
     162                 :            : 
     163                 :            : /* Structure used to pass parameters to extend_schedule_1.  */
     164                 :            : 
     165                 :            : struct extend_schedule_str {
     166                 :            :   int max;
     167                 :            :   isl_union_map *umap;
     168                 :            : };
     169                 :            : 
     170                 :            : /* Helper function for extend_schedule.  */
     171                 :            : 
     172                 :            : static isl_stat
     173                 :         54 : extend_schedule_1 (__isl_take isl_map *map, void *user)
     174                 :            : {
     175                 :         54 :   struct extend_schedule_str *str = (struct extend_schedule_str *) user;
     176                 :         54 :   str->umap = isl_union_map_add_map (str->umap, extend_map (map, str->max));
     177                 :         54 :   return isl_stat_ok;
     178                 :            : }
     179                 :            : 
     180                 :            : /* Return a relation that has uniform output dimensions.  */
     181                 :            : 
     182                 :            : static __isl_give isl_union_map *
     183                 :         43 : extend_schedule (__isl_take isl_union_map *x)
     184                 :            : {
     185                 :         43 :   int max = 0;
     186                 :         43 :   struct extend_schedule_str str;
     187                 :            : 
     188                 :         43 :   isl_union_map_foreach_map (x, max_number_of_out_dimensions, (void *) &max);
     189                 :         43 :   str.max = max;
     190                 :         43 :   str.umap = isl_union_map_empty (isl_union_map_get_space (x));
     191                 :         43 :   isl_union_map_foreach_map (x, extend_schedule_1, (void *) &str);
     192                 :         43 :   isl_union_map_free (x);
     193                 :         43 :   return isl_union_map_coalesce (str.umap);
     194                 :            : }
     195                 :            : 
     196                 :            : /* Applies SCHEDULE to the in and out dimensions of the dependences
     197                 :            :    DEPS and return the resulting relation.  */
     198                 :            : 
     199                 :            : static isl_map *
     200                 :         43 : apply_schedule_on_deps (__isl_keep isl_union_map *schedule,
     201                 :            :                         __isl_keep isl_union_map *deps)
     202                 :            : {
     203                 :         43 :   isl_union_map *trans = extend_schedule (isl_union_map_copy (schedule));
     204                 :         43 :   isl_union_map *ux = isl_union_map_copy (deps);
     205                 :         43 :   ux = isl_union_map_apply_domain (ux, isl_union_map_copy (trans));
     206                 :         43 :   ux = isl_union_map_apply_range (ux, trans);
     207                 :         43 :   ux = isl_union_map_coalesce (ux);
     208                 :            : 
     209                 :         43 :   if (!isl_union_map_is_empty (ux))
     210                 :         21 :     return isl_map_from_union_map (ux);
     211                 :            : 
     212                 :         22 :   isl_union_map_free (ux);
     213                 :         22 :   return NULL;
     214                 :            : }
     215                 :            : 
     216                 :            : /* Return true when DEPS is non empty and the intersection of LEX with
     217                 :            :    the DEPS transformed by SCHEDULE is non empty.  LEX is the relation
     218                 :            :    in which all the inputs before DEPTH occur at the same time as the
     219                 :            :    output, and the input at DEPTH occurs before output.  */
     220                 :            : 
     221                 :            : bool
     222                 :         45 : carries_deps (__isl_keep isl_union_map *schedule,
     223                 :            :               __isl_keep isl_union_map *deps,
     224                 :            :               int depth)
     225                 :            : {
     226                 :         45 :   if (isl_union_map_is_empty (deps))
     227                 :            :     return false;
     228                 :            : 
     229                 :         43 :   isl_map *x = apply_schedule_on_deps (schedule, deps);
     230                 :         43 :   if (x == NULL)
     231                 :            :     return false;
     232                 :            : 
     233                 :         21 :   isl_space *space = isl_map_get_space (x);
     234                 :         21 :   isl_map *lex = isl_map_lex_le (isl_space_range (space));
     235                 :         21 :   isl_constraint *ineq = isl_inequality_alloc
     236                 :         21 :     (isl_local_space_from_space (isl_map_get_space (x)));
     237                 :            : 
     238                 :         35 :   for (int i = 0; i < depth - 1; i++)
     239                 :         14 :     lex = isl_map_equate (lex, isl_dim_in, i, isl_dim_out, i);
     240                 :            : 
     241                 :            :   /* in + 1 <= out  */
     242                 :         21 :   ineq = isl_constraint_set_coefficient_si (ineq, isl_dim_out, depth - 1, 1);
     243                 :         21 :   ineq = isl_constraint_set_coefficient_si (ineq, isl_dim_in, depth - 1, -1);
     244                 :         21 :   ineq = isl_constraint_set_constant_si (ineq, -1);
     245                 :         21 :   lex = isl_map_add_constraint (lex, ineq);
     246                 :         21 :   lex = isl_map_coalesce (lex);
     247                 :         21 :   x = isl_map_intersect (x, lex);
     248                 :         21 :   bool res = !isl_map_is_empty (x);
     249                 :            : 
     250                 :         21 :   isl_map_free (x);
     251                 :         21 :   return res;
     252                 :            : }
     253                 :            : 
     254                 :            : /* Compute the dependence relations for the SCOP:
     255                 :            :    RAW are read after write dependences,
     256                 :            :    WAR are write after read dependences,
     257                 :            :    WAW are write after write dependences.  */
     258                 :            : 
     259                 :            : void
     260                 :        126 : scop_get_dependences (scop_p scop)
     261                 :            : {
     262                 :        126 :   if (scop->dependence)
     263                 :          0 :     return;
     264                 :            : 
     265                 :        126 :   isl_space *space = isl_set_get_space (scop->param_context);
     266                 :        126 :   isl_union_map *reads = isl_union_map_empty (isl_space_copy (space));
     267                 :        126 :   isl_union_map *must_writes = isl_union_map_empty (isl_space_copy (space));
     268                 :        126 :   isl_union_map *may_writes = isl_union_map_empty (space);
     269                 :        126 :   scop_get_reads_and_writes (scop, reads, must_writes, may_writes);
     270                 :            : 
     271                 :        126 :   if (dump_file)
     272                 :            :     {
     273                 :         60 :       fprintf (dump_file, "\n--- Documentation for datarefs dump: ---\n");
     274                 :         60 :       fprintf (dump_file, "Statements on the iteration domain are mapped to"
     275                 :            :                " array references.\n");
     276                 :         60 :       fprintf (dump_file, "  To read the following data references:\n\n");
     277                 :         60 :       fprintf (dump_file, "  S_5[i0] -> [106] : i0 >= 0 and i0 <= 3\n");
     278                 :         60 :       fprintf (dump_file, "  S_8[i0] -> [1, i0] : i0 >= 0 and i0 <= 3\n\n");
     279                 :            : 
     280                 :         60 :       fprintf (dump_file, "  S_5[i0] is the dynamic instance of statement"
     281                 :            :                " bb_5 in a loop that accesses all iterations 0 <= i0 <= 3.\n");
     282                 :         60 :       fprintf (dump_file, "  [1, i0] is a 'memref' with alias set 1"
     283                 :            :                " and first subscript access i0.\n");
     284                 :         60 :       fprintf (dump_file, "  [106] is a 'scalar reference' which is the sum of"
     285                 :            :                " SSA_NAME_VERSION 6"
     286                 :            :                " and --param graphite-max-arrays-per-scop=100\n");
     287                 :         60 :       fprintf (dump_file, "-----------------------\n\n");
     288                 :            : 
     289                 :         60 :       fprintf (dump_file, "data references (\n");
     290                 :         60 :       fprintf (dump_file, "  reads: ");
     291                 :         60 :       print_isl_union_map (dump_file, reads);
     292                 :         60 :       fprintf (dump_file, "  must_writes: ");
     293                 :         60 :       print_isl_union_map (dump_file, must_writes);
     294                 :         60 :       fprintf (dump_file, "  may_writes: ");
     295                 :         60 :       print_isl_union_map (dump_file, may_writes);
     296                 :         60 :       fprintf (dump_file, ")\n");
     297                 :            :     }
     298                 :            : 
     299                 :        126 :   gcc_assert (scop->original_schedule);
     300                 :            : 
     301                 :        126 :   isl_union_access_info *ai;
     302                 :        126 :   ai = isl_union_access_info_from_sink (isl_union_map_copy (reads));
     303                 :        126 :   ai = isl_union_access_info_set_must_source (ai, isl_union_map_copy (must_writes));
     304                 :        126 :   ai = isl_union_access_info_set_may_source (ai, may_writes);
     305                 :        126 :   ai = isl_union_access_info_set_schedule
     306                 :        126 :     (ai, isl_schedule_copy (scop->original_schedule));
     307                 :        126 :   isl_union_flow *flow = isl_union_access_info_compute_flow (ai);
     308                 :        126 :   isl_union_map *raw = isl_union_flow_get_must_dependence (flow);
     309                 :        126 :   isl_union_flow_free (flow);
     310                 :            : 
     311                 :        126 :   ai = isl_union_access_info_from_sink (isl_union_map_copy (must_writes));
     312                 :        126 :   ai = isl_union_access_info_set_must_source (ai, must_writes);
     313                 :        126 :   ai = isl_union_access_info_set_may_source (ai, reads);
     314                 :        126 :   ai = isl_union_access_info_set_schedule
     315                 :        126 :     (ai, isl_schedule_copy (scop->original_schedule));
     316                 :        126 :   flow = isl_union_access_info_compute_flow (ai);
     317                 :            : 
     318                 :        126 :   isl_union_map *waw = isl_union_flow_get_must_dependence (flow);
     319                 :        126 :   isl_union_map *war = isl_union_flow_get_may_dependence (flow);
     320                 :        126 :   war = isl_union_map_subtract (war, isl_union_map_copy (waw));
     321                 :        126 :   isl_union_flow_free (flow);
     322                 :            : 
     323                 :        126 :   raw = isl_union_map_coalesce (raw);
     324                 :        126 :   waw = isl_union_map_coalesce (waw);
     325                 :        126 :   war = isl_union_map_coalesce (war);
     326                 :            : 
     327                 :        126 :   isl_union_map *dependences = raw;
     328                 :        126 :   dependences = isl_union_map_union (dependences, war);
     329                 :        126 :   dependences = isl_union_map_union (dependences, waw);
     330                 :        126 :   dependences = isl_union_map_coalesce (dependences);
     331                 :            : 
     332                 :        126 :   if (dump_file)
     333                 :            :     {
     334                 :         60 :       fprintf (dump_file, "data dependences (\n");
     335                 :         60 :       print_isl_union_map (dump_file, dependences);
     336                 :         60 :       fprintf (dump_file, ")\n");
     337                 :            :     }
     338                 :            : 
     339                 :        126 :   scop->dependence = dependences;
     340                 :            : }
     341                 :            : 
     342                 :            : #endif /* HAVE_isl */

Generated by: LCOV version 1.0

LCOV profile is generated on x86_64 machine using following configure options: configure --disable-bootstrap --enable-coverage=opt --enable-languages=c,c++,fortran,go,jit,lto --enable-host-shared. GCC test suite is run with the built compiler.