LCOV - code coverage report
Current view: top level - gcc - graphite.h (source / functions) Hit Total Coverage
Test: gcc.info Lines: 20 22 90.9 %
Date: 2020-04-04 11:58:09 Functions: 0 0 -
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 0 -

           Branch data     Line data    Source code
       1                 :            : /* Graphite polyhedral representation.
       2                 :            :    Copyright (C) 2009-2020 Free Software Foundation, Inc.
       3                 :            :    Contributed by Sebastian Pop <sebastian.pop@amd.com> and
       4                 :            :    Tobias Grosser <grosser@fim.uni-passau.de>.
       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                 :            : #ifndef GCC_GRAPHITE_POLY_H
      23                 :            : #define GCC_GRAPHITE_POLY_H
      24                 :            : 
      25                 :            : #include "sese.h"
      26                 :            : #include <isl/options.h>
      27                 :            : #include <isl/ctx.h>
      28                 :            : #include <isl/val.h>
      29                 :            : #include <isl/set.h>
      30                 :            : #include <isl/union_set.h>
      31                 :            : #include <isl/map.h>
      32                 :            : #include <isl/union_map.h>
      33                 :            : #include <isl/aff.h>
      34                 :            : #include <isl/constraint.h>
      35                 :            : #include <isl/flow.h>
      36                 :            : #include <isl/ilp.h>
      37                 :            : #include <isl/schedule.h>
      38                 :            : #include <isl/ast_build.h>
      39                 :            : #include <isl/schedule_node.h>
      40                 :            : #include <isl/id.h>
      41                 :            : #include <isl/space.h>
      42                 :            : 
      43                 :            : typedef struct poly_dr *poly_dr_p;
      44                 :            : 
      45                 :            : typedef struct poly_bb *poly_bb_p;
      46                 :            : 
      47                 :            : typedef struct scop *scop_p;
      48                 :            : 
      49                 :            : typedef unsigned graphite_dim_t;
      50                 :            : 
      51                 :            : static inline graphite_dim_t scop_nb_params (scop_p);
      52                 :            : 
      53                 :            : /* A data reference can write or read some memory or we
      54                 :            :    just know it may write some memory.  */
      55                 :            : enum poly_dr_type
      56                 :            : {
      57                 :            :   PDR_READ,
      58                 :            :   /* PDR_MAY_READs are represented using PDR_READS.  This does not
      59                 :            :      limit the expressiveness.  */
      60                 :            :   PDR_WRITE,
      61                 :            :   PDR_MAY_WRITE
      62                 :            : };
      63                 :            : 
      64                 :            : struct poly_dr
      65                 :            : {
      66                 :            :   /* An identifier for this PDR.  */
      67                 :            :   int id;
      68                 :            : 
      69                 :            :   /* The number of data refs identical to this one in the PBB.  */
      70                 :            :   int nb_refs;
      71                 :            : 
      72                 :            :   /* A pointer to the gimple stmt containing this reference.  */
      73                 :            :   gimple *stmt;
      74                 :            : 
      75                 :            :   /* A pointer to the PBB that contains this data reference.  */
      76                 :            :   poly_bb_p pbb;
      77                 :            : 
      78                 :            :   enum poly_dr_type type;
      79                 :            : 
      80                 :            :   /* The access polyhedron contains the polyhedral space this data
      81                 :            :      reference will access.
      82                 :            : 
      83                 :            :      The polyhedron contains these dimensions:
      84                 :            : 
      85                 :            :      - The alias set (a):
      86                 :            :      Every memory access is classified in at least one alias set.
      87                 :            : 
      88                 :            :      - The subscripts (s_0, ..., s_n):
      89                 :            :      The memory is accessed using zero or more subscript dimensions.
      90                 :            : 
      91                 :            :      - The iteration domain (variables and parameters)
      92                 :            : 
      93                 :            :      Do not hardcode the dimensions.  Use the following accessor functions:
      94                 :            :      - pdr_alias_set_dim
      95                 :            :      - pdr_subscript_dim
      96                 :            :      - pdr_iterator_dim
      97                 :            :      - pdr_parameter_dim
      98                 :            : 
      99                 :            :      Example:
     100                 :            : 
     101                 :            :      | int A[1335][123];
     102                 :            :      | int *p = malloc ();
     103                 :            :      |
     104                 :            :      | k = ...
     105                 :            :      | for i
     106                 :            :      |   {
     107                 :            :      |     if (unknown_function ())
     108                 :            :      |       p = A;
     109                 :            :      |       ... = p[?][?];
     110                 :            :      |     for j
     111                 :            :      |       A[i][j+k] = m;
     112                 :            :      |   }
     113                 :            : 
     114                 :            :      The data access A[i][j+k] in alias set "5" is described like this:
     115                 :            : 
     116                 :            :      | i   j   k   a  s0  s1   1
     117                 :            :      | 0   0   0   1   0   0  -5     =  0
     118                 :            :      |-1   0   0   0   1   0   0     =  0
     119                 :            :      | 0  -1  -1   0   0   1   0     =  0
     120                 :            :      | 0   0   0   0   1   0   0     >= 0  # The last four lines describe the
     121                 :            :      | 0   0   0   0   0   1   0     >= 0  # array size.
     122                 :            :      | 0   0   0   0  -1   0 1335    >= 0
     123                 :            :      | 0   0   0   0   0  -1 123     >= 0
     124                 :            : 
     125                 :            :      The pointer "*p" in alias set "5" and "7" is described as a union of
     126                 :            :      polyhedron:
     127                 :            : 
     128                 :            : 
     129                 :            :      | i   k   a  s0   1
     130                 :            :      | 0   0   1   0  -5   =  0
     131                 :            :      | 0   0   0   1   0   >= 0
     132                 :            : 
     133                 :            :      "or"
     134                 :            : 
     135                 :            :      | i   k   a  s0   1
     136                 :            :      | 0   0   1   0  -7   =  0
     137                 :            :      | 0   0   0   1   0   >= 0
     138                 :            : 
     139                 :            :      "*p" accesses all of the object allocated with 'malloc'.
     140                 :            : 
     141                 :            :      The scalar data access "m" is represented as an array with zero subscript
     142                 :            :      dimensions.
     143                 :            : 
     144                 :            :      | i   j   k   a   1
     145                 :            :      | 0   0   0  -1   15  = 0
     146                 :            : 
     147                 :            :      The difference between the graphite internal format for access data and
     148                 :            :      the OpenSop format is in the order of columns.
     149                 :            :      Instead of having:
     150                 :            : 
     151                 :            :      | i   j   k   a  s0  s1   1
     152                 :            :      | 0   0   0   1   0   0  -5     =  0
     153                 :            :      |-1   0   0   0   1   0   0     =  0
     154                 :            :      | 0  -1  -1   0   0   1   0     =  0
     155                 :            :      | 0   0   0   0   1   0   0     >= 0  # The last four lines describe the
     156                 :            :      | 0   0   0   0   0   1   0     >= 0  # array size.
     157                 :            :      | 0   0   0   0  -1   0 1335    >= 0
     158                 :            :      | 0   0   0   0   0  -1 123     >= 0
     159                 :            : 
     160                 :            :      In OpenScop we have:
     161                 :            : 
     162                 :            :      | a  s0  s1   i   j   k   1
     163                 :            :      | 1   0   0   0   0   0  -5     =  0
     164                 :            :      | 0   1   0  -1   0   0   0     =  0
     165                 :            :      | 0   0   1   0  -1  -1   0     =  0
     166                 :            :      | 0   1   0   0   0   0   0     >= 0  # The last four lines describe the
     167                 :            :      | 0   0   1   0   0   0   0     >= 0  # array size.
     168                 :            :      | 0  -1   0   0   0   0 1335    >= 0
     169                 :            :      | 0   0  -1   0   0   0 123     >= 0
     170                 :            : 
     171                 :            :      The OpenScop access function is printed as follows:
     172                 :            : 
     173                 :            :      | 1  # The number of disjunct components in a union of access functions.
     174                 :            :      | R C O I L P  # Described bellow.
     175                 :            :      | a  s0  s1   i   j   k   1
     176                 :            :      | 1   0   0   0   0   0  -5     =  0
     177                 :            :      | 0   1   0  -1   0   0   0     =  0
     178                 :            :      | 0   0   1   0  -1  -1   0     =  0
     179                 :            :      | 0   1   0   0   0   0   0     >= 0  # The last four lines describe the
     180                 :            :      | 0   0   1   0   0   0   0     >= 0  # array size.
     181                 :            :      | 0  -1   0   0   0   0 1335    >= 0
     182                 :            :      | 0   0  -1   0   0   0 123     >= 0
     183                 :            : 
     184                 :            :      Where:
     185                 :            :      - R: Number of rows.
     186                 :            :      - C: Number of columns.
     187                 :            :      - O: Number of output dimensions = alias set + number of subscripts.
     188                 :            :      - I: Number of input dimensions (iterators).
     189                 :            :      - L: Number of local (existentially quantified) dimensions.
     190                 :            :      - P: Number of parameters.
     191                 :            : 
     192                 :            :      In the example, the vector "R C O I L P" is "7 7 3 2 0 1".  */
     193                 :            :   isl_map *accesses;
     194                 :            :   isl_set *subscript_sizes;
     195                 :            : };
     196                 :            : 
     197                 :            : #define PDR_ID(PDR) (PDR->id)
     198                 :            : #define PDR_NB_REFS(PDR) (PDR->nb_refs)
     199                 :            : #define PDR_PBB(PDR) (PDR->pbb)
     200                 :            : #define PDR_TYPE(PDR) (PDR->type)
     201                 :            : #define PDR_ACCESSES(PDR) (NULL)
     202                 :            : 
     203                 :            : void new_poly_dr (poly_bb_p, gimple *, enum poly_dr_type,
     204                 :            :                   isl_map *, isl_set *);
     205                 :            : void debug_pdr (poly_dr_p);
     206                 :            : void print_pdr (FILE *, poly_dr_p);
     207                 :            : 
     208                 :            : static inline bool
     209                 :       1370 : pdr_read_p (poly_dr_p pdr)
     210                 :            : {
     211                 :       1370 :   return PDR_TYPE (pdr) == PDR_READ;
     212                 :            : }
     213                 :            : 
     214                 :            : /* Returns true when PDR is a "write".  */
     215                 :            : 
     216                 :            : static inline bool
     217                 :        741 : pdr_write_p (poly_dr_p pdr)
     218                 :            : {
     219                 :        741 :   return PDR_TYPE (pdr) == PDR_WRITE;
     220                 :            : }
     221                 :            : 
     222                 :            : /* Returns true when PDR is a "may write".  */
     223                 :            : 
     224                 :            : static inline bool
     225                 :          0 : pdr_may_write_p (poly_dr_p pdr)
     226                 :            : {
     227                 :          0 :   return PDR_TYPE (pdr) == PDR_MAY_WRITE;
     228                 :            : }
     229                 :            : 
     230                 :            : /* POLY_BB represents a blackbox in the polyhedral model.  */
     231                 :            : 
     232                 :            : struct poly_bb
     233                 :            : {
     234                 :            :   /* Pointer to a basic block or a statement in the compiler.  */
     235                 :            :   gimple_poly_bb_p black_box;
     236                 :            : 
     237                 :            :   /* Pointer to the SCOP containing this PBB.  */
     238                 :            :   scop_p scop;
     239                 :            : 
     240                 :            :   /* The iteration domain of this bb.  The layout of this polyhedron
     241                 :            :      is I|G with I the iteration domain, G the context parameters.
     242                 :            : 
     243                 :            :      Example:
     244                 :            : 
     245                 :            :      for (i = a - 7*b + 8; i <= 3*a + 13*b + 20; i++)
     246                 :            :        for (j = 2; j <= 2*i + 5; j++)
     247                 :            :          for (k = 0; k <= 5; k++)
     248                 :            :            S (i,j,k)
     249                 :            : 
     250                 :            :      Loop iterators: i, j, k
     251                 :            :      Parameters: a, b
     252                 :            : 
     253                 :            :      | i >=  a -  7b +  8
     254                 :            :      | i <= 3a + 13b + 20
     255                 :            :      | j >= 2
     256                 :            :      | j <= 2i + 5
     257                 :            :      | k >= 0
     258                 :            :      | k <= 5
     259                 :            : 
     260                 :            :      The number of variables in the DOMAIN may change and is not
     261                 :            :      related to the number of loops in the original code.  */
     262                 :            :   isl_set *domain;
     263                 :            :   isl_set *iterators;
     264                 :            : 
     265                 :            :   /* The data references we access.  */
     266                 :            :   vec<poly_dr_p> drs;
     267                 :            : 
     268                 :            :   /* The last basic block generated for this pbb.  */
     269                 :            :   basic_block new_bb;
     270                 :            : };
     271                 :            : 
     272                 :            : #define PBB_BLACK_BOX(PBB) ((gimple_poly_bb_p) PBB->black_box)
     273                 :            : #define PBB_SCOP(PBB) (PBB->scop)
     274                 :            : #define PBB_DRS(PBB) (PBB->drs)
     275                 :            : 
     276                 :            : extern poly_bb_p new_poly_bb (scop_p, gimple_poly_bb_p);
     277                 :            : extern void print_pbb_domain (FILE *, poly_bb_p);
     278                 :            : extern void print_pbb (FILE *, poly_bb_p);
     279                 :            : extern void print_scop_context (FILE *, scop_p);
     280                 :            : extern void print_scop (FILE *, scop_p);
     281                 :            : extern void debug_pbb_domain (poly_bb_p);
     282                 :            : extern void debug_pbb (poly_bb_p);
     283                 :            : extern void print_pdrs (FILE *, poly_bb_p);
     284                 :            : extern void debug_pdrs (poly_bb_p);
     285                 :            : extern void debug_scop_context (scop_p);
     286                 :            : extern void debug_scop (scop_p);
     287                 :            : extern void print_scop_params (FILE *, scop_p);
     288                 :            : extern void debug_scop_params (scop_p);
     289                 :            : extern void print_iteration_domain (FILE *, poly_bb_p);
     290                 :            : extern void print_iteration_domains (FILE *, scop_p);
     291                 :            : extern void debug_iteration_domain (poly_bb_p);
     292                 :            : extern void debug_iteration_domains (scop_p);
     293                 :            : extern void print_isl_set (FILE *, isl_set *);
     294                 :            : extern void print_isl_map (FILE *, isl_map *);
     295                 :            : extern void print_isl_union_map (FILE *, isl_union_map *);
     296                 :            : extern void print_isl_aff (FILE *, isl_aff *);
     297                 :            : extern void print_isl_constraint (FILE *, isl_constraint *);
     298                 :            : extern void print_isl_schedule (FILE *, isl_schedule *);
     299                 :            : extern void debug_isl_schedule (isl_schedule *);
     300                 :            : extern void print_isl_ast (FILE *, isl_ast_node *);
     301                 :            : extern void debug_isl_ast (isl_ast_node *);
     302                 :            : extern void debug_isl_set (isl_set *);
     303                 :            : extern void debug_isl_map (isl_map *);
     304                 :            : extern void debug_isl_union_map (isl_union_map *);
     305                 :            : extern void debug_isl_aff (isl_aff *);
     306                 :            : extern void debug_isl_constraint (isl_constraint *);
     307                 :            : extern void debug_gmp_value (mpz_t);
     308                 :            : extern void debug_scop_pbb (scop_p scop, int i);
     309                 :            : extern void print_schedule_ast (FILE *, __isl_keep isl_schedule *, scop_p);
     310                 :            : extern void debug_schedule_ast (__isl_keep isl_schedule *, scop_p);
     311                 :            : 
     312                 :            : /* The basic block of the PBB.  */
     313                 :            : 
     314                 :            : static inline basic_block
     315                 :        842 : pbb_bb (poly_bb_p pbb)
     316                 :            : {
     317                 :        842 :   return GBB_BB (PBB_BLACK_BOX (pbb));
     318                 :            : }
     319                 :            : 
     320                 :            : static inline int
     321                 :        842 : pbb_index (poly_bb_p pbb)
     322                 :            : {
     323                 :        842 :   return pbb_bb (pbb)->index;
     324                 :            : }
     325                 :            : 
     326                 :            : /* The loop of the PBB.  */
     327                 :            : 
     328                 :            : static inline loop_p
     329                 :       5092 : pbb_loop (poly_bb_p pbb)
     330                 :            : {
     331                 :       3158 :   return gbb_loop (PBB_BLACK_BOX (pbb));
     332                 :            : }
     333                 :            : 
     334                 :            : /* The scop that contains the PDR.  */
     335                 :            : 
     336                 :            : static inline scop_p
     337                 :            : pdr_scop (poly_dr_p pdr)
     338                 :            : {
     339                 :            :   return PBB_SCOP (PDR_PBB (pdr));
     340                 :            : }
     341                 :            : 
     342                 :            : /* Set black box of PBB to BLACKBOX.  */
     343                 :            : 
     344                 :            : static inline void
     345                 :        578 : pbb_set_black_box (poly_bb_p pbb, gimple_poly_bb_p black_box)
     346                 :            : {
     347                 :        578 :   pbb->black_box = black_box;
     348                 :            : }
     349                 :            : 
     350                 :            : /* A helper structure to keep track of data references, polyhedral BBs, and
     351                 :            :    alias sets.  */
     352                 :            : 
     353                 :            : struct dr_info
     354                 :            : {
     355                 :            :   enum {
     356                 :            :     invalid_alias_set = -1
     357                 :            :   };
     358                 :            :   /* The data reference.  */
     359                 :            :   data_reference_p dr;
     360                 :            : 
     361                 :            :   /* The polyhedral BB containing this DR.  */
     362                 :            :   poly_bb_p pbb;
     363                 :            : 
     364                 :            :   /* ALIAS_SET is the SCC number assigned by a graph_dfs of the alias graph.
     365                 :            :      -1 is an invalid alias set.  */
     366                 :            :   int alias_set;
     367                 :            : 
     368                 :            :   /* Construct a DR_INFO from a data reference DR, an ALIAS_SET, and a PBB.  */
     369                 :        690 :   dr_info (data_reference_p dr, poly_bb_p pbb,
     370                 :            :            int alias_set = invalid_alias_set)
     371                 :        690 :     : dr (dr), pbb (pbb), alias_set (alias_set) {}
     372                 :            : };
     373                 :            : 
     374                 :            : /* A SCOP is a Static Control Part of the program, simple enough to be
     375                 :            :    represented in polyhedral form.  */
     376                 :            : struct scop
     377                 :            : {
     378                 :            :   /* A SCOP is defined as a SESE region.  */
     379                 :            :   sese_info_p scop_info;
     380                 :            : 
     381                 :            :   /* Number of parameters in SCoP.  */
     382                 :            :   graphite_dim_t nb_params;
     383                 :            : 
     384                 :            :   /* The maximum alias set as assigned to drs by build_alias_sets.  */
     385                 :            :   unsigned max_alias_set;
     386                 :            : 
     387                 :            :   /* All the basic blocks in this scop that contain memory references
     388                 :            :      and that will be represented as statements in the polyhedral
     389                 :            :      representation.  */
     390                 :            :   vec<poly_bb_p> pbbs;
     391                 :            : 
     392                 :            :   /* All the data references in this scop.  */
     393                 :            :   vec<dr_info> drs;
     394                 :            : 
     395                 :            :   /* The context describes known restrictions concerning the parameters
     396                 :            :      and relations in between the parameters.
     397                 :            : 
     398                 :            :   void f (int8_t a, uint_16_t b) {
     399                 :            :     c = 2 a + b;
     400                 :            :     ...
     401                 :            :   }
     402                 :            : 
     403                 :            :   Here we can add these restrictions to the context:
     404                 :            : 
     405                 :            :   -128 >= a >= 127
     406                 :            :      0 >= b >= 65,535
     407                 :            :      c = 2a + b  */
     408                 :            :   isl_set *param_context;
     409                 :            : 
     410                 :            :   /* The context used internally by isl.  */
     411                 :            :   isl_ctx *isl_context;
     412                 :            : 
     413                 :            :   /* SCoP original schedule.  */
     414                 :            :   isl_schedule *original_schedule;
     415                 :            : 
     416                 :            :   /* SCoP transformed schedule.  */
     417                 :            :   isl_schedule *transformed_schedule;
     418                 :            : 
     419                 :            :   /* The data dependence relation among the data references in this scop.  */
     420                 :            :   isl_union_map *dependence;
     421                 :            : };
     422                 :            : 
     423                 :            : extern scop_p new_scop (edge, edge);
     424                 :            : extern void free_scop (scop_p);
     425                 :            : extern gimple_poly_bb_p new_gimple_poly_bb (basic_block, vec<data_reference_p>,
     426                 :            :                                             vec<scalar_use>, vec<tree>);
     427                 :            : extern bool apply_poly_transforms (scop_p);
     428                 :            : 
     429                 :            : /* Set the region of SCOP to REGION.  */
     430                 :            : 
     431                 :            : static inline void
     432                 :        186 : scop_set_region (scop_p scop, sese_info_p region)
     433                 :            : {
     434                 :        186 :   scop->scop_info = region;
     435                 :            : }
     436                 :            : 
     437                 :            : /* Returns the number of parameters for SCOP.  */
     438                 :            : 
     439                 :            : static inline graphite_dim_t
     440                 :        176 : scop_nb_params (scop_p scop)
     441                 :            : {
     442                 :        176 :   return scop->nb_params;
     443                 :            : }
     444                 :            : 
     445                 :            : /* Set the number of params of SCOP to NB_PARAMS.  */
     446                 :            : 
     447                 :            : static inline void
     448                 :        176 : scop_set_nb_params (scop_p scop, graphite_dim_t nb_params)
     449                 :            : {
     450                 :        176 :   scop->nb_params = nb_params;
     451                 :            : }
     452                 :            : 
     453                 :            : extern void scop_get_dependences (scop_p scop);
     454                 :            : 
     455                 :            : bool
     456                 :            : carries_deps (__isl_keep isl_union_map *schedule,
     457                 :            :               __isl_keep isl_union_map *deps,
     458                 :            :               int depth);
     459                 :            : 
     460                 :            : extern bool build_poly_scop (scop_p);
     461                 :            : extern bool graphite_regenerate_ast_isl (scop_p);
     462                 :            : extern void build_scops (vec<scop_p> *);
     463                 :            : extern tree cached_scalar_evolution_in_region (const sese_l &, loop_p, tree);
     464                 :            : extern void dot_all_sese (FILE *, vec<sese_l> &);
     465                 :            : extern void dot_sese (sese_l &);
     466                 :            : extern void dot_cfg ();
     467                 :            : 
     468                 :            : #endif

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.