LCOV - code coverage report
Current view: top level - gcc - tree-data-ref.h (source / functions) Hit Total Coverage
Test: gcc.info Lines: 43 46 93.5 %
Date: 2020-04-04 11:58:09 Functions: 3 3 100.0 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 0 -

           Branch data     Line data    Source code
       1                 :            : /* Data references and dependences detectors.
       2                 :            :    Copyright (C) 2003-2020 Free Software Foundation, Inc.
       3                 :            :    Contributed by Sebastian Pop <pop@cri.ensmp.fr>
       4                 :            : 
       5                 :            : This file is part of GCC.
       6                 :            : 
       7                 :            : GCC is free software; you can redistribute it and/or modify it under
       8                 :            : the terms of the GNU General Public License as published by the Free
       9                 :            : Software Foundation; either version 3, or (at your option) any later
      10                 :            : version.
      11                 :            : 
      12                 :            : GCC is distributed in the hope that it will be useful, but WITHOUT ANY
      13                 :            : WARRANTY; without even the implied warranty of MERCHANTABILITY or
      14                 :            : FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
      15                 :            : for more details.
      16                 :            : 
      17                 :            : You should have received a copy of the GNU General Public License
      18                 :            : along with GCC; see the file COPYING3.  If not see
      19                 :            : <http://www.gnu.org/licenses/>.  */
      20                 :            : 
      21                 :            : #ifndef GCC_TREE_DATA_REF_H
      22                 :            : #define GCC_TREE_DATA_REF_H
      23                 :            : 
      24                 :            : #include "graphds.h"
      25                 :            : #include "tree-chrec.h"
      26                 :            : #include "opt-problem.h"
      27                 :            : 
      28                 :            : /*
      29                 :            :   innermost_loop_behavior describes the evolution of the address of the memory
      30                 :            :   reference in the innermost enclosing loop.  The address is expressed as
      31                 :            :   BASE + STEP * # of iteration, and base is further decomposed as the base
      32                 :            :   pointer (BASE_ADDRESS),  loop invariant offset (OFFSET) and
      33                 :            :   constant offset (INIT).  Examples, in loop nest
      34                 :            : 
      35                 :            :   for (i = 0; i < 100; i++)
      36                 :            :     for (j = 3; j < 100; j++)
      37                 :            : 
      38                 :            :                        Example 1                      Example 2
      39                 :            :       data-ref         a[j].b[i][j]                   *(p + x + 16B + 4B * j)
      40                 :            : 
      41                 :            : 
      42                 :            :   innermost_loop_behavior
      43                 :            :       base_address     &a                             p
      44                 :            :       offset           i * D_i                        x
      45                 :            :       init             3 * D_j + offsetof (b)         28
      46                 :            :       step             D_j                            4
      47                 :            : 
      48                 :            :   */
      49                 :            : struct innermost_loop_behavior
      50                 :            : {
      51                 :            :   tree base_address;
      52                 :            :   tree offset;
      53                 :            :   tree init;
      54                 :            :   tree step;
      55                 :            : 
      56                 :            :   /* BASE_ADDRESS is known to be misaligned by BASE_MISALIGNMENT bytes
      57                 :            :      from an alignment boundary of BASE_ALIGNMENT bytes.  For example,
      58                 :            :      if we had:
      59                 :            : 
      60                 :            :        struct S __attribute__((aligned(16))) { ... };
      61                 :            : 
      62                 :            :        char *ptr;
      63                 :            :        ... *(struct S *) (ptr - 4) ...;
      64                 :            : 
      65                 :            :      the information would be:
      66                 :            : 
      67                 :            :        base_address:      ptr
      68                 :            :        base_aligment:      16
      69                 :            :        base_misalignment:   4
      70                 :            :        init:               -4
      71                 :            : 
      72                 :            :      where init cancels the base misalignment.  If instead we had a
      73                 :            :      reference to a particular field:
      74                 :            : 
      75                 :            :        struct S __attribute__((aligned(16))) { ... int f; ... };
      76                 :            : 
      77                 :            :        char *ptr;
      78                 :            :        ... ((struct S *) (ptr - 4))->f ...;
      79                 :            : 
      80                 :            :      the information would be:
      81                 :            : 
      82                 :            :        base_address:      ptr
      83                 :            :        base_aligment:      16
      84                 :            :        base_misalignment:   4
      85                 :            :        init:               -4 + offsetof (S, f)
      86                 :            : 
      87                 :            :      where base_address + init might also be misaligned, and by a different
      88                 :            :      amount from base_address.  */
      89                 :            :   unsigned int base_alignment;
      90                 :            :   unsigned int base_misalignment;
      91                 :            : 
      92                 :            :   /* The largest power of two that divides OFFSET, capped to a suitably
      93                 :            :      high value if the offset is zero.  This is a byte rather than a bit
      94                 :            :      quantity.  */
      95                 :            :   unsigned int offset_alignment;
      96                 :            : 
      97                 :            :   /* Likewise for STEP.  */
      98                 :            :   unsigned int step_alignment;
      99                 :            : };
     100                 :            : 
     101                 :            : /* Describes the evolutions of indices of the memory reference.  The indices
     102                 :            :    are indices of the ARRAY_REFs, indexes in artificial dimensions
     103                 :            :    added for member selection of records and the operands of MEM_REFs.
     104                 :            :    BASE_OBJECT is the part of the reference that is loop-invariant
     105                 :            :    (note that this reference does not have to cover the whole object
     106                 :            :    being accessed, in which case UNCONSTRAINED_BASE is set; hence it is
     107                 :            :    not recommended to use BASE_OBJECT in any code generation).
     108                 :            :    For the examples above,
     109                 :            : 
     110                 :            :    base_object:        a                              *(p + x + 4B * j_0)
     111                 :            :    indices:            {j_0, +, 1}_2                  {16, +, 4}_2
     112                 :            :                        4
     113                 :            :                        {i_0, +, 1}_1
     114                 :            :                        {j_0, +, 1}_2
     115                 :            : */
     116                 :            : 
     117                 :            : struct indices
     118                 :            : {
     119                 :            :   /* The object.  */
     120                 :            :   tree base_object;
     121                 :            : 
     122                 :            :   /* A list of chrecs.  Access functions of the indices.  */
     123                 :            :   vec<tree> access_fns;
     124                 :            : 
     125                 :            :   /* Whether BASE_OBJECT is an access representing the whole object
     126                 :            :      or whether the access could not be constrained.  */
     127                 :            :   bool unconstrained_base;
     128                 :            : };
     129                 :            : 
     130                 :            : struct dr_alias
     131                 :            : {
     132                 :            :   /* The alias information that should be used for new pointers to this
     133                 :            :      location.  */
     134                 :            :   struct ptr_info_def *ptr_info;
     135                 :            : };
     136                 :            : 
     137                 :            : /* An integer vector.  A vector formally consists of an element of a vector
     138                 :            :    space. A vector space is a set that is closed under vector addition
     139                 :            :    and scalar multiplication.  In this vector space, an element is a list of
     140                 :            :    integers.  */
     141                 :            : typedef HOST_WIDE_INT lambda_int;
     142                 :            : typedef lambda_int *lambda_vector;
     143                 :            : 
     144                 :            : /* An integer matrix.  A matrix consists of m vectors of length n (IE
     145                 :            :    all vectors are the same length).  */
     146                 :            : typedef lambda_vector *lambda_matrix;
     147                 :            : 
     148                 :            : 
     149                 :            : 
     150                 :            : struct data_reference
     151                 :            : {
     152                 :            :   /* A pointer to the statement that contains this DR.  */
     153                 :            :   gimple *stmt;
     154                 :            : 
     155                 :            :   /* A pointer to the memory reference.  */
     156                 :            :   tree ref;
     157                 :            : 
     158                 :            :   /* Auxiliary info specific to a pass.  */
     159                 :            :   void *aux;
     160                 :            : 
     161                 :            :   /* True when the data reference is in RHS of a stmt.  */
     162                 :            :   bool is_read;
     163                 :            : 
     164                 :            :   /* True when the data reference is conditional within STMT,
     165                 :            :      i.e. if it might not occur even when the statement is executed
     166                 :            :      and runs to completion.  */
     167                 :            :   bool is_conditional_in_stmt;
     168                 :            : 
     169                 :            :   /* Behavior of the memory reference in the innermost loop.  */
     170                 :            :   struct innermost_loop_behavior innermost;
     171                 :            : 
     172                 :            :   /* Subscripts of this data reference.  */
     173                 :            :   struct indices indices;
     174                 :            : 
     175                 :            :   /* Alias information for the data reference.  */
     176                 :            :   struct dr_alias alias;
     177                 :            : };
     178                 :            : 
     179                 :            : #define DR_STMT(DR)                (DR)->stmt
     180                 :            : #define DR_REF(DR)                 (DR)->ref
     181                 :            : #define DR_BASE_OBJECT(DR)         (DR)->indices.base_object
     182                 :            : #define DR_UNCONSTRAINED_BASE(DR)  (DR)->indices.unconstrained_base
     183                 :            : #define DR_ACCESS_FNS(DR)          (DR)->indices.access_fns
     184                 :            : #define DR_ACCESS_FN(DR, I)        DR_ACCESS_FNS (DR)[I]
     185                 :            : #define DR_NUM_DIMENSIONS(DR)      DR_ACCESS_FNS (DR).length ()
     186                 :            : #define DR_IS_READ(DR)             (DR)->is_read
     187                 :            : #define DR_IS_WRITE(DR)            (!DR_IS_READ (DR))
     188                 :            : #define DR_IS_CONDITIONAL_IN_STMT(DR) (DR)->is_conditional_in_stmt
     189                 :            : #define DR_BASE_ADDRESS(DR)        (DR)->innermost.base_address
     190                 :            : #define DR_OFFSET(DR)              (DR)->innermost.offset
     191                 :            : #define DR_INIT(DR)                (DR)->innermost.init
     192                 :            : #define DR_STEP(DR)                (DR)->innermost.step
     193                 :            : #define DR_PTR_INFO(DR)            (DR)->alias.ptr_info
     194                 :            : #define DR_BASE_ALIGNMENT(DR)      (DR)->innermost.base_alignment
     195                 :            : #define DR_BASE_MISALIGNMENT(DR)   (DR)->innermost.base_misalignment
     196                 :            : #define DR_OFFSET_ALIGNMENT(DR)    (DR)->innermost.offset_alignment
     197                 :            : #define DR_STEP_ALIGNMENT(DR)      (DR)->innermost.step_alignment
     198                 :            : #define DR_INNERMOST(DR)           (DR)->innermost
     199                 :            : 
     200                 :            : typedef struct data_reference *data_reference_p;
     201                 :            : 
     202                 :            : /* This struct is used to store the information of a data reference,
     203                 :            :    including the data ref itself and the segment length for aliasing
     204                 :            :    checks.  This is used to merge alias checks.  */
     205                 :            : 
     206                 :            : class dr_with_seg_len
     207                 :            : {
     208                 :            : public:
     209                 :      20030 :   dr_with_seg_len (data_reference_p d, tree len, unsigned HOST_WIDE_INT size,
     210                 :            :                    unsigned int a)
     211                 :      20030 :     : dr (d), seg_len (len), access_size (size), align (a) {}
     212                 :            : 
     213                 :            :   data_reference_p dr;
     214                 :            :   /* The offset of the last access that needs to be checked minus
     215                 :            :      the offset of the first.  */
     216                 :            :   tree seg_len;
     217                 :            :   /* A value that, when added to abs (SEG_LEN), gives the total number of
     218                 :            :      bytes in the segment.  */
     219                 :            :   poly_uint64 access_size;
     220                 :            :   /* The minimum common alignment of DR's start address, SEG_LEN and
     221                 :            :      ACCESS_SIZE.  */
     222                 :            :   unsigned int align;
     223                 :            : };
     224                 :            : 
     225                 :            : /* Flags that describe a potential alias between two dr_with_seg_lens.
     226                 :            :    In general, each pair of dr_with_seg_lens represents a composite of
     227                 :            :    multiple access pairs P, so testing flags like DR_IS_READ on the DRs
     228                 :            :    does not give meaningful information.
     229                 :            : 
     230                 :            :    DR_ALIAS_RAW:
     231                 :            :         There is a pair in P for which the second reference is a read
     232                 :            :         and the first is a write.
     233                 :            : 
     234                 :            :    DR_ALIAS_WAR:
     235                 :            :         There is a pair in P for which the second reference is a write
     236                 :            :         and the first is a read.
     237                 :            : 
     238                 :            :    DR_ALIAS_WAW:
     239                 :            :         There is a pair in P for which both references are writes.
     240                 :            : 
     241                 :            :    DR_ALIAS_ARBITRARY:
     242                 :            :         Either
     243                 :            :         (a) it isn't possible to classify one pair in P as RAW, WAW or WAR; or
     244                 :            :         (b) there is a pair in P that breaks the ordering assumption below.
     245                 :            : 
     246                 :            :         This flag overrides the RAW, WAR and WAW flags above.
     247                 :            : 
     248                 :            :    DR_ALIAS_UNSWAPPED:
     249                 :            :    DR_ALIAS_SWAPPED:
     250                 :            :         Temporary flags that indicate whether there is a pair P whose
     251                 :            :         DRs have or haven't been swapped around.
     252                 :            : 
     253                 :            :    DR_ALIAS_MIXED_STEPS:
     254                 :            :         The DR_STEP for one of the data references in the pair does not
     255                 :            :         accurately describe that reference for all members of P.  (Note
     256                 :            :         that the flag does not say anything about whether the DR_STEPs
     257                 :            :         of the two references in the pair are the same.)
     258                 :            : 
     259                 :            :    The ordering assumption mentioned above is that for every pair
     260                 :            :    (DR_A, DR_B) in P:
     261                 :            : 
     262                 :            :    (1) The original code accesses n elements for DR_A and n elements for DR_B,
     263                 :            :        interleaved as follows:
     264                 :            : 
     265                 :            :          one access of size DR_A.access_size at DR_A.dr
     266                 :            :          one access of size DR_B.access_size at DR_B.dr
     267                 :            :          one access of size DR_A.access_size at DR_A.dr + STEP_A
     268                 :            :          one access of size DR_B.access_size at DR_B.dr + STEP_B
     269                 :            :          one access of size DR_A.access_size at DR_A.dr + STEP_A * 2
     270                 :            :          one access of size DR_B.access_size at DR_B.dr + STEP_B * 2
     271                 :            :          ...
     272                 :            : 
     273                 :            :    (2) The new code accesses the same data in exactly two chunks:
     274                 :            : 
     275                 :            :          one group of accesses spanning |DR_A.seg_len| + DR_A.access_size
     276                 :            :          one group of accesses spanning |DR_B.seg_len| + DR_B.access_size
     277                 :            : 
     278                 :            :    A pair might break this assumption if the DR_A and DR_B accesses
     279                 :            :    in the original or the new code are mingled in some way.  For example,
     280                 :            :    if DR_A.access_size represents the effect of two individual writes
     281                 :            :    to nearby locations, the pair breaks the assumption if those writes
     282                 :            :    occur either side of the access for DR_B.
     283                 :            : 
     284                 :            :    Note that DR_ALIAS_ARBITRARY describes whether the ordering assumption
     285                 :            :    fails to hold for any individual pair in P.  If the assumption *does*
     286                 :            :    hold for every pair in P, it doesn't matter whether it holds for the
     287                 :            :    composite pair or not.  In other words, P should represent the complete
     288                 :            :    set of pairs that the composite pair is testing, so only the ordering
     289                 :            :    of two accesses in the same member of P matters.  */
     290                 :            : const unsigned int DR_ALIAS_RAW = 1U << 0;
     291                 :            : const unsigned int DR_ALIAS_WAR = 1U << 1;
     292                 :            : const unsigned int DR_ALIAS_WAW = 1U << 2;
     293                 :            : const unsigned int DR_ALIAS_ARBITRARY = 1U << 3;
     294                 :            : const unsigned int DR_ALIAS_SWAPPED = 1U << 4;
     295                 :            : const unsigned int DR_ALIAS_UNSWAPPED = 1U << 5;
     296                 :            : const unsigned int DR_ALIAS_MIXED_STEPS = 1U << 6;
     297                 :            : 
     298                 :            : /* This struct contains two dr_with_seg_len objects with aliasing data
     299                 :            :    refs.  Two comparisons are generated from them.  */
     300                 :            : 
     301                 :            : class dr_with_seg_len_pair_t
     302                 :            : {
     303                 :            : public:
     304                 :            :   /* WELL_ORDERED indicates that the ordering assumption described above
     305                 :            :      DR_ALIAS_ARBITRARY holds.  REORDERED indicates that it doesn't.  */
     306                 :            :   enum sequencing { WELL_ORDERED, REORDERED };
     307                 :            : 
     308                 :            :   dr_with_seg_len_pair_t (const dr_with_seg_len &,
     309                 :            :                           const dr_with_seg_len &, sequencing);
     310                 :            : 
     311                 :            :   dr_with_seg_len first;
     312                 :            :   dr_with_seg_len second;
     313                 :            :   unsigned int flags;
     314                 :            : };
     315                 :            : 
     316                 :      20030 : inline dr_with_seg_len_pair_t::
     317                 :            : dr_with_seg_len_pair_t (const dr_with_seg_len &d1, const dr_with_seg_len &d2,
     318                 :      20030 :                         sequencing seq)
     319                 :      20030 :   : first (d1), second (d2), flags (0)
     320                 :            : {
     321                 :      20030 :   if (DR_IS_READ (d1.dr) && DR_IS_WRITE (d2.dr))
     322                 :       6753 :     flags |= DR_ALIAS_WAR;
     323                 :      13277 :   else if (DR_IS_WRITE (d1.dr) && DR_IS_READ (d2.dr))
     324                 :       1428 :     flags |= DR_ALIAS_RAW;
     325                 :      11849 :   else if (DR_IS_WRITE (d1.dr) && DR_IS_WRITE (d2.dr))
     326                 :      11849 :     flags |= DR_ALIAS_WAW;
     327                 :            :   else
     328                 :          0 :     gcc_unreachable ();
     329                 :      20030 :   if (seq == REORDERED)
     330                 :       1068 :     flags |= DR_ALIAS_ARBITRARY;
     331                 :      20030 : }
     332                 :            : 
     333                 :            : enum data_dependence_direction {
     334                 :            :   dir_positive,
     335                 :            :   dir_negative,
     336                 :            :   dir_equal,
     337                 :            :   dir_positive_or_negative,
     338                 :            :   dir_positive_or_equal,
     339                 :            :   dir_negative_or_equal,
     340                 :            :   dir_star,
     341                 :            :   dir_independent
     342                 :            : };
     343                 :            : 
     344                 :            : /* The description of the grid of iterations that overlap.  At most
     345                 :            :    two loops are considered at the same time just now, hence at most
     346                 :            :    two functions are needed.  For each of the functions, we store
     347                 :            :    the vector of coefficients, f[0] + x * f[1] + y * f[2] + ...,
     348                 :            :    where x, y, ... are variables.  */
     349                 :            : 
     350                 :            : #define MAX_DIM 2
     351                 :            : 
     352                 :            : /* Special values of N.  */
     353                 :            : #define NO_DEPENDENCE 0
     354                 :            : #define NOT_KNOWN (MAX_DIM + 1)
     355                 :            : #define CF_NONTRIVIAL_P(CF) ((CF)->n != NO_DEPENDENCE && (CF)->n != NOT_KNOWN)
     356                 :            : #define CF_NOT_KNOWN_P(CF) ((CF)->n == NOT_KNOWN)
     357                 :            : #define CF_NO_DEPENDENCE_P(CF) ((CF)->n == NO_DEPENDENCE)
     358                 :            : 
     359                 :            : typedef vec<tree> affine_fn;
     360                 :            : 
     361                 :            : struct conflict_function
     362                 :            : {
     363                 :            :   unsigned n;
     364                 :            :   affine_fn fns[MAX_DIM];
     365                 :            : };
     366                 :            : 
     367                 :            : /* What is a subscript?  Given two array accesses a subscript is the
     368                 :            :    tuple composed of the access functions for a given dimension.
     369                 :            :    Example: Given A[f1][f2][f3] and B[g1][g2][g3], there are three
     370                 :            :    subscripts: (f1, g1), (f2, g2), (f3, g3).  These three subscripts
     371                 :            :    are stored in the data_dependence_relation structure under the form
     372                 :            :    of an array of subscripts.  */
     373                 :            : 
     374                 :            : struct subscript
     375                 :            : {
     376                 :            :   /* The access functions of the two references.  */
     377                 :            :   tree access_fn[2];
     378                 :            : 
     379                 :            :   /* A description of the iterations for which the elements are
     380                 :            :      accessed twice.  */
     381                 :            :   conflict_function *conflicting_iterations_in_a;
     382                 :            :   conflict_function *conflicting_iterations_in_b;
     383                 :            : 
     384                 :            :   /* This field stores the information about the iteration domain
     385                 :            :      validity of the dependence relation.  */
     386                 :            :   tree last_conflict;
     387                 :            : 
     388                 :            :   /* Distance from the iteration that access a conflicting element in
     389                 :            :      A to the iteration that access this same conflicting element in
     390                 :            :      B.  The distance is a tree scalar expression, i.e. a constant or a
     391                 :            :      symbolic expression, but certainly not a chrec function.  */
     392                 :            :   tree distance;
     393                 :            : };
     394                 :            : 
     395                 :            : typedef struct subscript *subscript_p;
     396                 :            : 
     397                 :            : #define SUB_ACCESS_FN(SUB, I) (SUB)->access_fn[I]
     398                 :            : #define SUB_CONFLICTS_IN_A(SUB) (SUB)->conflicting_iterations_in_a
     399                 :            : #define SUB_CONFLICTS_IN_B(SUB) (SUB)->conflicting_iterations_in_b
     400                 :            : #define SUB_LAST_CONFLICT(SUB) (SUB)->last_conflict
     401                 :            : #define SUB_DISTANCE(SUB) (SUB)->distance
     402                 :            : 
     403                 :            : /* A data_dependence_relation represents a relation between two
     404                 :            :    data_references A and B.  */
     405                 :            : 
     406                 :            : struct data_dependence_relation
     407                 :            : {
     408                 :            : 
     409                 :            :   struct data_reference *a;
     410                 :            :   struct data_reference *b;
     411                 :            : 
     412                 :            :   /* A "yes/no/maybe" field for the dependence relation:
     413                 :            : 
     414                 :            :      - when "ARE_DEPENDENT == NULL_TREE", there exist a dependence
     415                 :            :        relation between A and B, and the description of this relation
     416                 :            :        is given in the SUBSCRIPTS array,
     417                 :            : 
     418                 :            :      - when "ARE_DEPENDENT == chrec_known", there is no dependence and
     419                 :            :        SUBSCRIPTS is empty,
     420                 :            : 
     421                 :            :      - when "ARE_DEPENDENT == chrec_dont_know", there may be a dependence,
     422                 :            :        but the analyzer cannot be more specific.  */
     423                 :            :   tree are_dependent;
     424                 :            : 
     425                 :            :   /* If nonnull, COULD_BE_INDEPENDENT_P is true and the accesses are
     426                 :            :      independent when the runtime addresses of OBJECT_A and OBJECT_B
     427                 :            :      are different.  The addresses of both objects are invariant in the
     428                 :            :      loop nest.  */
     429                 :            :   tree object_a;
     430                 :            :   tree object_b;
     431                 :            : 
     432                 :            :   /* For each subscript in the dependence test, there is an element in
     433                 :            :      this array.  This is the attribute that labels the edge A->B of
     434                 :            :      the data_dependence_relation.  */
     435                 :            :   vec<subscript_p> subscripts;
     436                 :            : 
     437                 :            :   /* The analyzed loop nest.  */
     438                 :            :   vec<loop_p> loop_nest;
     439                 :            : 
     440                 :            :   /* The classic direction vector.  */
     441                 :            :   vec<lambda_vector> dir_vects;
     442                 :            : 
     443                 :            :   /* The classic distance vector.  */
     444                 :            :   vec<lambda_vector> dist_vects;
     445                 :            : 
     446                 :            :   /* Is the dependence reversed with respect to the lexicographic order?  */
     447                 :            :   bool reversed_p;
     448                 :            : 
     449                 :            :   /* When the dependence relation is affine, it can be represented by
     450                 :            :      a distance vector.  */
     451                 :            :   bool affine_p;
     452                 :            : 
     453                 :            :   /* Set to true when the dependence relation is on the same data
     454                 :            :      access.  */
     455                 :            :   bool self_reference_p;
     456                 :            : 
     457                 :            :   /* True if the dependence described is conservatively correct rather
     458                 :            :      than exact, and if it is still possible for the accesses to be
     459                 :            :      conditionally independent.  For example, the a and b references in:
     460                 :            : 
     461                 :            :        struct s *a, *b;
     462                 :            :        for (int i = 0; i < n; ++i)
     463                 :            :          a->f[i] += b->f[i];
     464                 :            : 
     465                 :            :      conservatively have a distance vector of (0), for the case in which
     466                 :            :      a == b, but the accesses are independent if a != b.  Similarly,
     467                 :            :      the a and b references in:
     468                 :            : 
     469                 :            :        struct s *a, *b;
     470                 :            :        for (int i = 0; i < n; ++i)
     471                 :            :          a[0].f[i] += b[i].f[i];
     472                 :            : 
     473                 :            :      conservatively have a distance vector of (0), but they are indepenent
     474                 :            :      when a != b + i.  In contrast, the references in:
     475                 :            : 
     476                 :            :        struct s *a;
     477                 :            :        for (int i = 0; i < n; ++i)
     478                 :            :          a->f[i] += a->f[i];
     479                 :            : 
     480                 :            :      have the same distance vector of (0), but the accesses can never be
     481                 :            :      independent.  */
     482                 :            :   bool could_be_independent_p;
     483                 :            : };
     484                 :            : 
     485                 :            : typedef struct data_dependence_relation *ddr_p;
     486                 :            : 
     487                 :            : #define DDR_A(DDR) (DDR)->a
     488                 :            : #define DDR_B(DDR) (DDR)->b
     489                 :            : #define DDR_AFFINE_P(DDR) (DDR)->affine_p
     490                 :            : #define DDR_ARE_DEPENDENT(DDR) (DDR)->are_dependent
     491                 :            : #define DDR_OBJECT_A(DDR) (DDR)->object_a
     492                 :            : #define DDR_OBJECT_B(DDR) (DDR)->object_b
     493                 :            : #define DDR_SUBSCRIPTS(DDR) (DDR)->subscripts
     494                 :            : #define DDR_SUBSCRIPT(DDR, I) DDR_SUBSCRIPTS (DDR)[I]
     495                 :            : #define DDR_NUM_SUBSCRIPTS(DDR) DDR_SUBSCRIPTS (DDR).length ()
     496                 :            : 
     497                 :            : #define DDR_LOOP_NEST(DDR) (DDR)->loop_nest
     498                 :            : /* The size of the direction/distance vectors: the number of loops in
     499                 :            :    the loop nest.  */
     500                 :            : #define DDR_NB_LOOPS(DDR) (DDR_LOOP_NEST (DDR).length ())
     501                 :            : #define DDR_SELF_REFERENCE(DDR) (DDR)->self_reference_p
     502                 :            : 
     503                 :            : #define DDR_DIST_VECTS(DDR) ((DDR)->dist_vects)
     504                 :            : #define DDR_DIR_VECTS(DDR) ((DDR)->dir_vects)
     505                 :            : #define DDR_NUM_DIST_VECTS(DDR) \
     506                 :            :   (DDR_DIST_VECTS (DDR).length ())
     507                 :            : #define DDR_NUM_DIR_VECTS(DDR) \
     508                 :            :   (DDR_DIR_VECTS (DDR).length ())
     509                 :            : #define DDR_DIR_VECT(DDR, I) \
     510                 :            :   DDR_DIR_VECTS (DDR)[I]
     511                 :            : #define DDR_DIST_VECT(DDR, I) \
     512                 :            :   DDR_DIST_VECTS (DDR)[I]
     513                 :            : #define DDR_REVERSED_P(DDR) (DDR)->reversed_p
     514                 :            : #define DDR_COULD_BE_INDEPENDENT_P(DDR) (DDR)->could_be_independent_p
     515                 :            : 
     516                 :            : 
     517                 :            : opt_result dr_analyze_innermost (innermost_loop_behavior *, tree,
     518                 :            :                                  class loop *, const gimple *);
     519                 :            : extern bool compute_data_dependences_for_loop (class loop *, bool,
     520                 :            :                                                vec<loop_p> *,
     521                 :            :                                                vec<data_reference_p> *,
     522                 :            :                                                vec<ddr_p> *);
     523                 :            : extern void debug_ddrs (vec<ddr_p> );
     524                 :            : extern void dump_data_reference (FILE *, struct data_reference *);
     525                 :            : extern void debug (data_reference &ref);
     526                 :            : extern void debug (data_reference *ptr);
     527                 :            : extern void debug_data_reference (struct data_reference *);
     528                 :            : extern void debug_data_references (vec<data_reference_p> );
     529                 :            : extern void debug (vec<data_reference_p> &ref);
     530                 :            : extern void debug (vec<data_reference_p> *ptr);
     531                 :            : extern void debug_data_dependence_relation (struct data_dependence_relation *);
     532                 :            : extern void dump_data_dependence_relations (FILE *, vec<ddr_p> );
     533                 :            : extern void debug (vec<ddr_p> &ref);
     534                 :            : extern void debug (vec<ddr_p> *ptr);
     535                 :            : extern void debug_data_dependence_relations (vec<ddr_p> );
     536                 :            : extern void free_dependence_relation (struct data_dependence_relation *);
     537                 :            : extern void free_dependence_relations (vec<ddr_p> );
     538                 :            : extern void free_data_ref (data_reference_p);
     539                 :            : extern void free_data_refs (vec<data_reference_p> );
     540                 :            : extern opt_result find_data_references_in_stmt (class loop *, gimple *,
     541                 :            :                                                 vec<data_reference_p> *);
     542                 :            : extern bool graphite_find_data_references_in_stmt (edge, loop_p, gimple *,
     543                 :            :                                                    vec<data_reference_p> *);
     544                 :            : tree find_data_references_in_loop (class loop *, vec<data_reference_p> *);
     545                 :            : bool loop_nest_has_data_refs (loop_p loop);
     546                 :            : struct data_reference *create_data_ref (edge, loop_p, tree, gimple *, bool,
     547                 :            :                                         bool);
     548                 :            : extern bool find_loop_nest (class loop *, vec<loop_p> *);
     549                 :            : extern struct data_dependence_relation *initialize_data_dependence_relation
     550                 :            :      (struct data_reference *, struct data_reference *, vec<loop_p>);
     551                 :            : extern void compute_affine_dependence (struct data_dependence_relation *,
     552                 :            :                                        loop_p);
     553                 :            : extern void compute_self_dependence (struct data_dependence_relation *);
     554                 :            : extern bool compute_all_dependences (vec<data_reference_p> ,
     555                 :            :                                      vec<ddr_p> *,
     556                 :            :                                      vec<loop_p>, bool);
     557                 :            : extern tree find_data_references_in_bb (class loop *, basic_block,
     558                 :            :                                         vec<data_reference_p> *);
     559                 :            : extern unsigned int dr_alignment (innermost_loop_behavior *);
     560                 :            : extern tree get_base_for_alignment (tree, unsigned int *);
     561                 :            : 
     562                 :            : /* Return the alignment in bytes that DR is guaranteed to have at all
     563                 :            :    times.  */
     564                 :            : 
     565                 :            : inline unsigned int
     566                 :            : dr_alignment (data_reference *dr)
     567                 :            : {
     568                 :            :   return dr_alignment (&DR_INNERMOST (dr));
     569                 :            : }
     570                 :            : 
     571                 :            : extern bool dr_may_alias_p (const struct data_reference *,
     572                 :            :                             const struct data_reference *, class loop *);
     573                 :            : extern bool dr_equal_offsets_p (struct data_reference *,
     574                 :            :                                 struct data_reference *);
     575                 :            : 
     576                 :            : extern opt_result runtime_alias_check_p (ddr_p, class loop *, bool);
     577                 :            : extern int data_ref_compare_tree (tree, tree);
     578                 :            : extern void prune_runtime_alias_test_list (vec<dr_with_seg_len_pair_t> *,
     579                 :            :                                            poly_uint64);
     580                 :            : extern void create_runtime_alias_checks (class loop *,
     581                 :            :                                          vec<dr_with_seg_len_pair_t> *, tree*);
     582                 :            : extern tree dr_direction_indicator (struct data_reference *);
     583                 :            : extern tree dr_zero_step_indicator (struct data_reference *);
     584                 :            : extern bool dr_known_forward_stride_p (struct data_reference *);
     585                 :            : 
     586                 :            : /* Return true when the base objects of data references A and B are
     587                 :            :    the same memory object.  */
     588                 :            : 
     589                 :            : static inline bool
     590                 :            : same_data_refs_base_objects (data_reference_p a, data_reference_p b)
     591                 :            : {
     592                 :            :   return DR_NUM_DIMENSIONS (a) == DR_NUM_DIMENSIONS (b)
     593                 :            :     && operand_equal_p (DR_BASE_OBJECT (a), DR_BASE_OBJECT (b), 0);
     594                 :            : }
     595                 :            : 
     596                 :            : /* Return true when the data references A and B are accessing the same
     597                 :            :    memory object with the same access functions.  */
     598                 :            : 
     599                 :            : static inline bool
     600                 :            : same_data_refs (data_reference_p a, data_reference_p b)
     601                 :            : {
     602                 :            :   unsigned int i;
     603                 :            : 
     604                 :            :   /* The references are exactly the same.  */
     605                 :            :   if (operand_equal_p (DR_REF (a), DR_REF (b), 0))
     606                 :            :     return true;
     607                 :            : 
     608                 :            :   if (!same_data_refs_base_objects (a, b))
     609                 :            :     return false;
     610                 :            : 
     611                 :            :   for (i = 0; i < DR_NUM_DIMENSIONS (a); i++)
     612                 :            :     if (!eq_evolutions_p (DR_ACCESS_FN (a, i), DR_ACCESS_FN (b, i)))
     613                 :            :       return false;
     614                 :            : 
     615                 :            :   return true;
     616                 :            : }
     617                 :            : 
     618                 :            : /* Returns true when all the dependences are computable.  */
     619                 :            : 
     620                 :            : inline bool
     621                 :            : known_dependences_p (vec<ddr_p> dependence_relations)
     622                 :            : {
     623                 :            :   ddr_p ddr;
     624                 :            :   unsigned int i;
     625                 :            : 
     626                 :            :   FOR_EACH_VEC_ELT (dependence_relations, i, ddr)
     627                 :            :     if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
     628                 :            :       return false;
     629                 :            : 
     630                 :            :   return true;
     631                 :            : }
     632                 :            : 
     633                 :            : /* Returns the dependence level for a vector DIST of size LENGTH.
     634                 :            :    LEVEL = 0 means a lexicographic dependence, i.e. a dependence due
     635                 :            :    to the sequence of statements, not carried by any loop.  */
     636                 :            : 
     637                 :            : static inline unsigned
     638                 :        148 : dependence_level (lambda_vector dist_vect, int length)
     639                 :            : {
     640                 :            :   int i;
     641                 :            : 
     642                 :        539 :   for (i = 0; i < length; i++)
     643                 :        414 :     if (dist_vect[i] != 0)
     644                 :        203 :       return i + 1;
     645                 :            : 
     646                 :            :   return 0;
     647                 :            : }
     648                 :            : 
     649                 :            : /* Return the dependence level for the DDR relation.  */
     650                 :            : 
     651                 :            : static inline unsigned
     652                 :            : ddr_dependence_level (ddr_p ddr)
     653                 :            : {
     654                 :            :   unsigned vector;
     655                 :            :   unsigned level = 0;
     656                 :            : 
     657                 :            :   if (DDR_DIST_VECTS (ddr).exists ())
     658                 :            :     level = dependence_level (DDR_DIST_VECT (ddr, 0), DDR_NB_LOOPS (ddr));
     659                 :            : 
     660                 :            :   for (vector = 1; vector < DDR_NUM_DIST_VECTS (ddr); vector++)
     661                 :            :     level = MIN (level, dependence_level (DDR_DIST_VECT (ddr, vector),
     662                 :            :                                           DDR_NB_LOOPS (ddr)));
     663                 :            :   return level;
     664                 :            : }
     665                 :            : 
     666                 :            : /* Return the index of the variable VAR in the LOOP_NEST array.  */
     667                 :            : 
     668                 :            : static inline int
     669                 :      44092 : index_in_loop_nest (int var, vec<loop_p> loop_nest)
     670                 :            : {
     671                 :      44092 :   class loop *loopi;
     672                 :      44092 :   int var_index;
     673                 :            : 
     674                 :      48443 :   for (var_index = 0; loop_nest.iterate (var_index, &loopi); var_index++)
     675                 :      48443 :     if (loopi->num == var)
     676                 :      44092 :       return var_index;
     677                 :            : 
     678                 :          0 :   gcc_unreachable ();
     679                 :            : }
     680                 :            : 
     681                 :            : /* Returns true when the data reference DR the form "A[i] = ..."
     682                 :            :    with a stride equal to its unit type size.  */
     683                 :            : 
     684                 :            : static inline bool
     685                 :            : adjacent_dr_p (struct data_reference *dr)
     686                 :            : {
     687                 :            :   /* If this is a bitfield store bail out.  */
     688                 :            :   if (TREE_CODE (DR_REF (dr)) == COMPONENT_REF
     689                 :            :       && DECL_BIT_FIELD (TREE_OPERAND (DR_REF (dr), 1)))
     690                 :            :     return false;
     691                 :            : 
     692                 :            :   if (!DR_STEP (dr)
     693                 :            :       || TREE_CODE (DR_STEP (dr)) != INTEGER_CST)
     694                 :            :     return false;
     695                 :            : 
     696                 :            :   return tree_int_cst_equal (fold_unary (ABS_EXPR, TREE_TYPE (DR_STEP (dr)),
     697                 :            :                                          DR_STEP (dr)),
     698                 :            :                              TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr))));
     699                 :            : }
     700                 :            : 
     701                 :            : void split_constant_offset (tree , tree *, tree *);
     702                 :            : 
     703                 :            : /* Compute the greatest common divisor of a VECTOR of SIZE numbers.  */
     704                 :            : 
     705                 :            : static inline lambda_int
     706                 :            : lambda_vector_gcd (lambda_vector vector, int size)
     707                 :            : {
     708                 :            :   int i;
     709                 :            :   lambda_int gcd1 = 0;
     710                 :            : 
     711                 :            :   if (size > 0)
     712                 :            :     {
     713                 :            :       gcd1 = vector[0];
     714                 :            :       for (i = 1; i < size; i++)
     715                 :            :         gcd1 = gcd (gcd1, vector[i]);
     716                 :            :     }
     717                 :            :   return gcd1;
     718                 :            : }
     719                 :            : 
     720                 :            : /* Allocate a new vector of given SIZE.  */
     721                 :            : 
     722                 :            : static inline lambda_vector
     723                 :     534738 : lambda_vector_new (int size)
     724                 :            : {
     725                 :            :   /* ???  We shouldn't abuse the GC allocator here.  */
     726                 :     534738 :   return ggc_cleared_vec_alloc<lambda_int> (size);
     727                 :            : }
     728                 :            : 
     729                 :            : /* Clear out vector VEC1 of length SIZE.  */
     730                 :            : 
     731                 :            : static inline void
     732                 :        571 : lambda_vector_clear (lambda_vector vec1, int size)
     733                 :            : {
     734                 :        571 :   memset (vec1, 0, size * sizeof (*vec1));
     735                 :          0 : }
     736                 :            : 
     737                 :            : /* Returns true when the vector V is lexicographically positive, in
     738                 :            :    other words, when the first nonzero element is positive.  */
     739                 :            : 
     740                 :            : static inline bool
     741                 :       7211 : lambda_vector_lexico_pos (lambda_vector v,
     742                 :            :                           unsigned n)
     743                 :            : {
     744                 :            :   unsigned i;
     745                 :       7911 :   for (i = 0; i < n; i++)
     746                 :            :     {
     747                 :       7338 :       if (v[i] == 0)
     748                 :        641 :         continue;
     749                 :       6697 :       if (v[i] < 0)
     750                 :            :         return false;
     751                 :            :       if (v[i] > 0)
     752                 :            :         return true;
     753                 :            :     }
     754                 :            :   return true;
     755                 :            : }
     756                 :            : 
     757                 :            : /* Return true if vector VEC1 of length SIZE is the zero vector.  */
     758                 :            : 
     759                 :            : static inline bool
     760                 :      34814 : lambda_vector_zerop (lambda_vector vec1, int size)
     761                 :            : {
     762                 :            :   int i;
     763                 :      67436 :   for (i = 0; i < size; i++)
     764                 :      34718 :     if (vec1[i] != 0)
     765                 :            :       return false;
     766                 :            :   return true;
     767                 :            : }
     768                 :            : 
     769                 :            : /* Allocate a matrix of M rows x  N cols.  */
     770                 :            : 
     771                 :            : static inline lambda_matrix
     772                 :    1537966 : lambda_matrix_new (int m, int n, struct obstack *lambda_obstack)
     773                 :            : {
     774                 :    1537966 :   lambda_matrix mat;
     775                 :    1537966 :   int i;
     776                 :            : 
     777                 :    1537966 :   mat = XOBNEWVEC (lambda_obstack, lambda_vector, m);
     778                 :            : 
     779                 :    4613212 :   for (i = 0; i < m; i++)
     780                 :    3075246 :     mat[i] = XOBNEWVEC (lambda_obstack, lambda_int, n);
     781                 :            : 
     782                 :    1537966 :   return mat;
     783                 :            : }
     784                 :            : 
     785                 :            : #endif  /* GCC_TREE_DATA_REF_H  */

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.