LCOV - code coverage report
Current view: top level - gcc - tree-data-ref.h (source / functions) Coverage Total Hit
Test: gcc.info Lines: 95.0 % 60 57
Test Date: 2024-03-23 14:05:01 Functions: 100.0 % 5 5
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-2024 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                 :             :   /* Alias information for the data reference.  */
     170                 :             :   struct dr_alias alias;
     171                 :             : 
     172                 :             :   /* Behavior of the memory reference in the innermost loop.  */
     173                 :             :   struct innermost_loop_behavior innermost;
     174                 :             : 
     175                 :             :   /* Subscripts of this data reference.  */
     176                 :             :   struct indices indices;
     177                 :             : 
     178                 :             :   /* Alternate subscripts initialized lazily and used by data-dependence
     179                 :             :      analysis only when the main indices of two DRs are not comparable.
     180                 :             :      Keep last to keep vec_info_shared::check_datarefs happy.  */
     181                 :             :   struct indices alt_indices;
     182                 :             : };
     183                 :             : 
     184                 :             : #define DR_STMT(DR)                (DR)->stmt
     185                 :             : #define DR_REF(DR)                 (DR)->ref
     186                 :             : #define DR_BASE_OBJECT(DR)         (DR)->indices.base_object
     187                 :             : #define DR_UNCONSTRAINED_BASE(DR)  (DR)->indices.unconstrained_base
     188                 :             : #define DR_ACCESS_FNS(DR)          (DR)->indices.access_fns
     189                 :             : #define DR_ACCESS_FN(DR, I)        DR_ACCESS_FNS (DR)[I]
     190                 :             : #define DR_NUM_DIMENSIONS(DR)      DR_ACCESS_FNS (DR).length ()
     191                 :             : #define DR_IS_READ(DR)             (DR)->is_read
     192                 :             : #define DR_IS_WRITE(DR)            (!DR_IS_READ (DR))
     193                 :             : #define DR_IS_CONDITIONAL_IN_STMT(DR) (DR)->is_conditional_in_stmt
     194                 :             : #define DR_BASE_ADDRESS(DR)        (DR)->innermost.base_address
     195                 :             : #define DR_OFFSET(DR)              (DR)->innermost.offset
     196                 :             : #define DR_INIT(DR)                (DR)->innermost.init
     197                 :             : #define DR_STEP(DR)                (DR)->innermost.step
     198                 :             : #define DR_PTR_INFO(DR)            (DR)->alias.ptr_info
     199                 :             : #define DR_BASE_ALIGNMENT(DR)      (DR)->innermost.base_alignment
     200                 :             : #define DR_BASE_MISALIGNMENT(DR)   (DR)->innermost.base_misalignment
     201                 :             : #define DR_OFFSET_ALIGNMENT(DR)    (DR)->innermost.offset_alignment
     202                 :             : #define DR_STEP_ALIGNMENT(DR)      (DR)->innermost.step_alignment
     203                 :             : #define DR_INNERMOST(DR)           (DR)->innermost
     204                 :             : 
     205                 :             : typedef struct data_reference *data_reference_p;
     206                 :             : 
     207                 :             : /* This struct is used to store the information of a data reference,
     208                 :             :    including the data ref itself and the segment length for aliasing
     209                 :             :    checks.  This is used to merge alias checks.  */
     210                 :             : 
     211                 :             : class dr_with_seg_len
     212                 :             : {
     213                 :             : public:
     214                 :       46499 :   dr_with_seg_len (data_reference_p d, tree len, unsigned HOST_WIDE_INT size,
     215                 :             :                    unsigned int a)
     216                 :       46499 :     : dr (d), seg_len (len), access_size (size), align (a) {}
     217                 :             : 
     218                 :             :   data_reference_p dr;
     219                 :             :   /* The offset of the last access that needs to be checked minus
     220                 :             :      the offset of the first.  */
     221                 :             :   tree seg_len;
     222                 :             :   /* A value that, when added to abs (SEG_LEN), gives the total number of
     223                 :             :      bytes in the segment.  */
     224                 :             :   poly_uint64 access_size;
     225                 :             :   /* The minimum common alignment of DR's start address, SEG_LEN and
     226                 :             :      ACCESS_SIZE.  */
     227                 :             :   unsigned int align;
     228                 :             : };
     229                 :             : 
     230                 :             : /* Flags that describe a potential alias between two dr_with_seg_lens.
     231                 :             :    In general, each pair of dr_with_seg_lens represents a composite of
     232                 :             :    multiple access pairs P, so testing flags like DR_IS_READ on the DRs
     233                 :             :    does not give meaningful information.
     234                 :             : 
     235                 :             :    DR_ALIAS_RAW:
     236                 :             :         There is a pair in P for which the second reference is a read
     237                 :             :         and the first is a write.
     238                 :             : 
     239                 :             :    DR_ALIAS_WAR:
     240                 :             :         There is a pair in P for which the second reference is a write
     241                 :             :         and the first is a read.
     242                 :             : 
     243                 :             :    DR_ALIAS_WAW:
     244                 :             :         There is a pair in P for which both references are writes.
     245                 :             : 
     246                 :             :    DR_ALIAS_ARBITRARY:
     247                 :             :         Either
     248                 :             :         (a) it isn't possible to classify one pair in P as RAW, WAW or WAR; or
     249                 :             :         (b) there is a pair in P that breaks the ordering assumption below.
     250                 :             : 
     251                 :             :         This flag overrides the RAW, WAR and WAW flags above.
     252                 :             : 
     253                 :             :    DR_ALIAS_UNSWAPPED:
     254                 :             :    DR_ALIAS_SWAPPED:
     255                 :             :         Temporary flags that indicate whether there is a pair P whose
     256                 :             :         DRs have or haven't been swapped around.
     257                 :             : 
     258                 :             :    DR_ALIAS_MIXED_STEPS:
     259                 :             :         The DR_STEP for one of the data references in the pair does not
     260                 :             :         accurately describe that reference for all members of P.  (Note
     261                 :             :         that the flag does not say anything about whether the DR_STEPs
     262                 :             :         of the two references in the pair are the same.)
     263                 :             : 
     264                 :             :    The ordering assumption mentioned above is that for every pair
     265                 :             :    (DR_A, DR_B) in P:
     266                 :             : 
     267                 :             :    (1) The original code accesses n elements for DR_A and n elements for DR_B,
     268                 :             :        interleaved as follows:
     269                 :             : 
     270                 :             :          one access of size DR_A.access_size at DR_A.dr
     271                 :             :          one access of size DR_B.access_size at DR_B.dr
     272                 :             :          one access of size DR_A.access_size at DR_A.dr + STEP_A
     273                 :             :          one access of size DR_B.access_size at DR_B.dr + STEP_B
     274                 :             :          one access of size DR_A.access_size at DR_A.dr + STEP_A * 2
     275                 :             :          one access of size DR_B.access_size at DR_B.dr + STEP_B * 2
     276                 :             :          ...
     277                 :             : 
     278                 :             :    (2) The new code accesses the same data in exactly two chunks:
     279                 :             : 
     280                 :             :          one group of accesses spanning |DR_A.seg_len| + DR_A.access_size
     281                 :             :          one group of accesses spanning |DR_B.seg_len| + DR_B.access_size
     282                 :             : 
     283                 :             :    A pair might break this assumption if the DR_A and DR_B accesses
     284                 :             :    in the original or the new code are mingled in some way.  For example,
     285                 :             :    if DR_A.access_size represents the effect of two individual writes
     286                 :             :    to nearby locations, the pair breaks the assumption if those writes
     287                 :             :    occur either side of the access for DR_B.
     288                 :             : 
     289                 :             :    Note that DR_ALIAS_ARBITRARY describes whether the ordering assumption
     290                 :             :    fails to hold for any individual pair in P.  If the assumption *does*
     291                 :             :    hold for every pair in P, it doesn't matter whether it holds for the
     292                 :             :    composite pair or not.  In other words, P should represent the complete
     293                 :             :    set of pairs that the composite pair is testing, so only the ordering
     294                 :             :    of two accesses in the same member of P matters.  */
     295                 :             : const unsigned int DR_ALIAS_RAW = 1U << 0;
     296                 :             : const unsigned int DR_ALIAS_WAR = 1U << 1;
     297                 :             : const unsigned int DR_ALIAS_WAW = 1U << 2;
     298                 :             : const unsigned int DR_ALIAS_ARBITRARY = 1U << 3;
     299                 :             : const unsigned int DR_ALIAS_SWAPPED = 1U << 4;
     300                 :             : const unsigned int DR_ALIAS_UNSWAPPED = 1U << 5;
     301                 :             : const unsigned int DR_ALIAS_MIXED_STEPS = 1U << 6;
     302                 :             : 
     303                 :             : /* This struct contains two dr_with_seg_len objects with aliasing data
     304                 :             :    refs.  Two comparisons are generated from them.  */
     305                 :             : 
     306                 :             : class dr_with_seg_len_pair_t
     307                 :             : {
     308                 :             : public:
     309                 :             :   /* WELL_ORDERED indicates that the ordering assumption described above
     310                 :             :      DR_ALIAS_ARBITRARY holds.  REORDERED indicates that it doesn't.  */
     311                 :             :   enum sequencing { WELL_ORDERED, REORDERED };
     312                 :             : 
     313                 :             :   dr_with_seg_len_pair_t (const dr_with_seg_len &,
     314                 :             :                           const dr_with_seg_len &, sequencing);
     315                 :             : 
     316                 :             :   dr_with_seg_len first;
     317                 :             :   dr_with_seg_len second;
     318                 :             :   unsigned int flags;
     319                 :             : };
     320                 :             : 
     321                 :       46499 : inline dr_with_seg_len_pair_t::
     322                 :             : dr_with_seg_len_pair_t (const dr_with_seg_len &d1, const dr_with_seg_len &d2,
     323                 :       46499 :                         sequencing seq)
     324                 :       46499 :   : first (d1), second (d2), flags (0)
     325                 :             : {
     326                 :       46499 :   if (DR_IS_READ (d1.dr) && DR_IS_WRITE (d2.dr))
     327                 :       24001 :     flags |= DR_ALIAS_WAR;
     328                 :       22498 :   else if (DR_IS_WRITE (d1.dr) && DR_IS_READ (d2.dr))
     329                 :        6227 :     flags |= DR_ALIAS_RAW;
     330                 :       16271 :   else if (DR_IS_WRITE (d1.dr) && DR_IS_WRITE (d2.dr))
     331                 :       16271 :     flags |= DR_ALIAS_WAW;
     332                 :             :   else
     333                 :           0 :     gcc_unreachable ();
     334                 :       46499 :   if (seq == REORDERED)
     335                 :        5330 :     flags |= DR_ALIAS_ARBITRARY;
     336                 :       46499 : }
     337                 :             : 
     338                 :             : enum data_dependence_direction {
     339                 :             :   dir_positive,
     340                 :             :   dir_negative,
     341                 :             :   dir_equal,
     342                 :             :   dir_positive_or_negative,
     343                 :             :   dir_positive_or_equal,
     344                 :             :   dir_negative_or_equal,
     345                 :             :   dir_star,
     346                 :             :   dir_independent
     347                 :             : };
     348                 :             : 
     349                 :             : /* The description of the grid of iterations that overlap.  At most
     350                 :             :    two loops are considered at the same time just now, hence at most
     351                 :             :    two functions are needed.  For each of the functions, we store
     352                 :             :    the vector of coefficients, f[0] + x * f[1] + y * f[2] + ...,
     353                 :             :    where x, y, ... are variables.  */
     354                 :             : 
     355                 :             : #define MAX_DIM 2
     356                 :             : 
     357                 :             : /* Special values of N.  */
     358                 :             : #define NO_DEPENDENCE 0
     359                 :             : #define NOT_KNOWN (MAX_DIM + 1)
     360                 :             : #define CF_NONTRIVIAL_P(CF) ((CF)->n != NO_DEPENDENCE && (CF)->n != NOT_KNOWN)
     361                 :             : #define CF_NOT_KNOWN_P(CF) ((CF)->n == NOT_KNOWN)
     362                 :             : #define CF_NO_DEPENDENCE_P(CF) ((CF)->n == NO_DEPENDENCE)
     363                 :             : 
     364                 :             : typedef vec<tree> affine_fn;
     365                 :             : 
     366                 :             : struct conflict_function
     367                 :             : {
     368                 :             :   unsigned n;
     369                 :             :   affine_fn fns[MAX_DIM];
     370                 :             : };
     371                 :             : 
     372                 :             : /* What is a subscript?  Given two array accesses a subscript is the
     373                 :             :    tuple composed of the access functions for a given dimension.
     374                 :             :    Example: Given A[f1][f2][f3] and B[g1][g2][g3], there are three
     375                 :             :    subscripts: (f1, g1), (f2, g2), (f3, g3).  These three subscripts
     376                 :             :    are stored in the data_dependence_relation structure under the form
     377                 :             :    of an array of subscripts.  */
     378                 :             : 
     379                 :             : struct subscript
     380                 :             : {
     381                 :             :   /* The access functions of the two references.  */
     382                 :             :   tree access_fn[2];
     383                 :             : 
     384                 :             :   /* A description of the iterations for which the elements are
     385                 :             :      accessed twice.  */
     386                 :             :   conflict_function *conflicting_iterations_in_a;
     387                 :             :   conflict_function *conflicting_iterations_in_b;
     388                 :             : 
     389                 :             :   /* This field stores the information about the iteration domain
     390                 :             :      validity of the dependence relation.  */
     391                 :             :   tree last_conflict;
     392                 :             : 
     393                 :             :   /* Distance from the iteration that access a conflicting element in
     394                 :             :      A to the iteration that access this same conflicting element in
     395                 :             :      B.  The distance is a tree scalar expression, i.e. a constant or a
     396                 :             :      symbolic expression, but certainly not a chrec function.  */
     397                 :             :   tree distance;
     398                 :             : };
     399                 :             : 
     400                 :             : typedef struct subscript *subscript_p;
     401                 :             : 
     402                 :             : #define SUB_ACCESS_FN(SUB, I) (SUB)->access_fn[I]
     403                 :             : #define SUB_CONFLICTS_IN_A(SUB) (SUB)->conflicting_iterations_in_a
     404                 :             : #define SUB_CONFLICTS_IN_B(SUB) (SUB)->conflicting_iterations_in_b
     405                 :             : #define SUB_LAST_CONFLICT(SUB) (SUB)->last_conflict
     406                 :             : #define SUB_DISTANCE(SUB) (SUB)->distance
     407                 :             : 
     408                 :             : /* A data_dependence_relation represents a relation between two
     409                 :             :    data_references A and B.  */
     410                 :             : 
     411                 :             : struct data_dependence_relation
     412                 :             : {
     413                 :             : 
     414                 :             :   struct data_reference *a;
     415                 :             :   struct data_reference *b;
     416                 :             : 
     417                 :             :   /* A "yes/no/maybe" field for the dependence relation:
     418                 :             : 
     419                 :             :      - when "ARE_DEPENDENT == NULL_TREE", there exist a dependence
     420                 :             :        relation between A and B, and the description of this relation
     421                 :             :        is given in the SUBSCRIPTS array,
     422                 :             : 
     423                 :             :      - when "ARE_DEPENDENT == chrec_known", there is no dependence and
     424                 :             :        SUBSCRIPTS is empty,
     425                 :             : 
     426                 :             :      - when "ARE_DEPENDENT == chrec_dont_know", there may be a dependence,
     427                 :             :        but the analyzer cannot be more specific.  */
     428                 :             :   tree are_dependent;
     429                 :             : 
     430                 :             :   /* If nonnull, COULD_BE_INDEPENDENT_P is true and the accesses are
     431                 :             :      independent when the runtime addresses of OBJECT_A and OBJECT_B
     432                 :             :      are different.  The addresses of both objects are invariant in the
     433                 :             :      loop nest.  */
     434                 :             :   tree object_a;
     435                 :             :   tree object_b;
     436                 :             : 
     437                 :             :   /* For each subscript in the dependence test, there is an element in
     438                 :             :      this array.  This is the attribute that labels the edge A->B of
     439                 :             :      the data_dependence_relation.  */
     440                 :             :   vec<subscript_p> subscripts;
     441                 :             : 
     442                 :             :   /* The analyzed loop nest.  */
     443                 :             :   vec<loop_p> loop_nest;
     444                 :             : 
     445                 :             :   /* The classic direction vector.  */
     446                 :             :   vec<lambda_vector> dir_vects;
     447                 :             : 
     448                 :             :   /* The classic distance vector.  */
     449                 :             :   vec<lambda_vector> dist_vects;
     450                 :             : 
     451                 :             :   /* Is the dependence reversed with respect to the lexicographic order?  */
     452                 :             :   bool reversed_p;
     453                 :             : 
     454                 :             :   /* When the dependence relation is affine, it can be represented by
     455                 :             :      a distance vector.  */
     456                 :             :   bool affine_p;
     457                 :             : 
     458                 :             :   /* Set to true when the dependence relation is on the same data
     459                 :             :      access.  */
     460                 :             :   bool self_reference_p;
     461                 :             : 
     462                 :             :   /* True if the dependence described is conservatively correct rather
     463                 :             :      than exact, and if it is still possible for the accesses to be
     464                 :             :      conditionally independent.  For example, the a and b references in:
     465                 :             : 
     466                 :             :        struct s *a, *b;
     467                 :             :        for (int i = 0; i < n; ++i)
     468                 :             :          a->f[i] += b->f[i];
     469                 :             : 
     470                 :             :      conservatively have a distance vector of (0), for the case in which
     471                 :             :      a == b, but the accesses are independent if a != b.  Similarly,
     472                 :             :      the a and b references in:
     473                 :             : 
     474                 :             :        struct s *a, *b;
     475                 :             :        for (int i = 0; i < n; ++i)
     476                 :             :          a[0].f[i] += b[i].f[i];
     477                 :             : 
     478                 :             :      conservatively have a distance vector of (0), but they are indepenent
     479                 :             :      when a != b + i.  In contrast, the references in:
     480                 :             : 
     481                 :             :        struct s *a;
     482                 :             :        for (int i = 0; i < n; ++i)
     483                 :             :          a->f[i] += a->f[i];
     484                 :             : 
     485                 :             :      have the same distance vector of (0), but the accesses can never be
     486                 :             :      independent.  */
     487                 :             :   bool could_be_independent_p;
     488                 :             : };
     489                 :             : 
     490                 :             : typedef struct data_dependence_relation *ddr_p;
     491                 :             : 
     492                 :             : #define DDR_A(DDR) (DDR)->a
     493                 :             : #define DDR_B(DDR) (DDR)->b
     494                 :             : #define DDR_AFFINE_P(DDR) (DDR)->affine_p
     495                 :             : #define DDR_ARE_DEPENDENT(DDR) (DDR)->are_dependent
     496                 :             : #define DDR_OBJECT_A(DDR) (DDR)->object_a
     497                 :             : #define DDR_OBJECT_B(DDR) (DDR)->object_b
     498                 :             : #define DDR_SUBSCRIPTS(DDR) (DDR)->subscripts
     499                 :             : #define DDR_SUBSCRIPT(DDR, I) DDR_SUBSCRIPTS (DDR)[I]
     500                 :             : #define DDR_NUM_SUBSCRIPTS(DDR) DDR_SUBSCRIPTS (DDR).length ()
     501                 :             : 
     502                 :             : #define DDR_LOOP_NEST(DDR) (DDR)->loop_nest
     503                 :             : /* The size of the direction/distance vectors: the number of loops in
     504                 :             :    the loop nest.  */
     505                 :             : #define DDR_NB_LOOPS(DDR) (DDR_LOOP_NEST (DDR).length ())
     506                 :             : #define DDR_SELF_REFERENCE(DDR) (DDR)->self_reference_p
     507                 :             : 
     508                 :             : #define DDR_DIST_VECTS(DDR) ((DDR)->dist_vects)
     509                 :             : #define DDR_DIR_VECTS(DDR) ((DDR)->dir_vects)
     510                 :             : #define DDR_NUM_DIST_VECTS(DDR) \
     511                 :             :   (DDR_DIST_VECTS (DDR).length ())
     512                 :             : #define DDR_NUM_DIR_VECTS(DDR) \
     513                 :             :   (DDR_DIR_VECTS (DDR).length ())
     514                 :             : #define DDR_DIR_VECT(DDR, I) \
     515                 :             :   DDR_DIR_VECTS (DDR)[I]
     516                 :             : #define DDR_DIST_VECT(DDR, I) \
     517                 :             :   DDR_DIST_VECTS (DDR)[I]
     518                 :             : #define DDR_REVERSED_P(DDR) (DDR)->reversed_p
     519                 :             : #define DDR_COULD_BE_INDEPENDENT_P(DDR) (DDR)->could_be_independent_p
     520                 :             : 
     521                 :             : 
     522                 :             : opt_result dr_analyze_innermost (innermost_loop_behavior *, tree,
     523                 :             :                                  class loop *, const gimple *);
     524                 :             : extern bool compute_data_dependences_for_loop (class loop *, bool,
     525                 :             :                                                vec<loop_p> *,
     526                 :             :                                                vec<data_reference_p> *,
     527                 :             :                                                vec<ddr_p> *);
     528                 :             : extern void debug_ddrs (vec<ddr_p> );
     529                 :             : extern void dump_data_reference (FILE *, struct data_reference *);
     530                 :             : extern void debug (data_reference &ref);
     531                 :             : extern void debug (data_reference *ptr);
     532                 :             : extern void debug_data_reference (struct data_reference *);
     533                 :             : extern void debug_data_references (vec<data_reference_p> );
     534                 :             : extern void debug (vec<data_reference_p> &ref);
     535                 :             : extern void debug (vec<data_reference_p> *ptr);
     536                 :             : extern void debug_data_dependence_relation (const data_dependence_relation *);
     537                 :             : extern void dump_data_dependence_relations (FILE *, const vec<ddr_p> &);
     538                 :             : extern void debug (vec<ddr_p> &ref);
     539                 :             : extern void debug (vec<ddr_p> *ptr);
     540                 :             : extern void debug_data_dependence_relations (vec<ddr_p> );
     541                 :             : extern void free_dependence_relation (struct data_dependence_relation *);
     542                 :             : extern void free_dependence_relations (vec<ddr_p>& );
     543                 :             : extern void free_data_ref (data_reference_p);
     544                 :             : extern void free_data_refs (vec<data_reference_p>& );
     545                 :             : extern opt_result find_data_references_in_stmt (class loop *, gimple *,
     546                 :             :                                                 vec<data_reference_p> *);
     547                 :             : extern bool graphite_find_data_references_in_stmt (edge, loop_p, gimple *,
     548                 :             :                                                    vec<data_reference_p> *);
     549                 :             : tree find_data_references_in_loop (class loop *, vec<data_reference_p> *);
     550                 :             : bool loop_nest_has_data_refs (loop_p loop);
     551                 :             : struct data_reference *create_data_ref (edge, loop_p, tree, gimple *, bool,
     552                 :             :                                         bool);
     553                 :             : extern bool find_loop_nest (class loop *, vec<loop_p> *);
     554                 :             : extern struct data_dependence_relation *initialize_data_dependence_relation
     555                 :             :      (struct data_reference *, struct data_reference *, vec<loop_p>);
     556                 :             : extern void compute_affine_dependence (struct data_dependence_relation *,
     557                 :             :                                        loop_p);
     558                 :             : extern void compute_self_dependence (struct data_dependence_relation *);
     559                 :             : extern bool compute_all_dependences (const vec<data_reference_p> &,
     560                 :             :                                      vec<ddr_p> *,
     561                 :             :                                      const vec<loop_p> &, bool);
     562                 :             : extern tree find_data_references_in_bb (class loop *, basic_block,
     563                 :             :                                         vec<data_reference_p> *);
     564                 :             : extern unsigned int dr_alignment (innermost_loop_behavior *);
     565                 :             : extern tree get_base_for_alignment (tree, unsigned int *);
     566                 :             : 
     567                 :             : /* Return the alignment in bytes that DR is guaranteed to have at all
     568                 :             :    times.  */
     569                 :             : 
     570                 :             : inline unsigned int
     571                 :       94374 : dr_alignment (data_reference *dr)
     572                 :             : {
     573                 :       47187 :   return dr_alignment (&DR_INNERMOST (dr));
     574                 :             : }
     575                 :             : 
     576                 :             : extern bool dr_may_alias_p (const struct data_reference *,
     577                 :             :                             const struct data_reference *, class loop *);
     578                 :             : extern bool dr_equal_offsets_p (struct data_reference *,
     579                 :             :                                 struct data_reference *);
     580                 :             : 
     581                 :             : extern opt_result runtime_alias_check_p (ddr_p, class loop *, bool);
     582                 :             : extern int data_ref_compare_tree (tree, tree);
     583                 :             : extern void prune_runtime_alias_test_list (vec<dr_with_seg_len_pair_t> *,
     584                 :             :                                            poly_uint64);
     585                 :             : extern void create_runtime_alias_checks (class loop *,
     586                 :             :                                          const vec<dr_with_seg_len_pair_t> *,
     587                 :             :                                          tree*);
     588                 :             : extern tree dr_direction_indicator (struct data_reference *);
     589                 :             : extern tree dr_zero_step_indicator (struct data_reference *);
     590                 :             : extern bool dr_known_forward_stride_p (struct data_reference *);
     591                 :             : 
     592                 :             : /* Return true when the base objects of data references A and B are
     593                 :             :    the same memory object.  */
     594                 :             : 
     595                 :             : inline bool
     596                 :          58 : same_data_refs_base_objects (data_reference_p a, data_reference_p b)
     597                 :             : {
     598                 :          99 :   return DR_NUM_DIMENSIONS (a) == DR_NUM_DIMENSIONS (b)
     599                 :          58 :     && operand_equal_p (DR_BASE_OBJECT (a), DR_BASE_OBJECT (b), 0);
     600                 :             : }
     601                 :             : 
     602                 :             : /* Return true when the data references A and B are accessing the same
     603                 :             :    memory object with the same access functions.  Optionally skip the
     604                 :             :    last OFFSET dimensions in the data reference.  */
     605                 :             : 
     606                 :             : inline bool
     607                 :          58 : same_data_refs (data_reference_p a, data_reference_p b, int offset = 0)
     608                 :             : {
     609                 :          58 :   unsigned int i;
     610                 :             : 
     611                 :             :   /* The references are exactly the same.  */
     612                 :          58 :   if (operand_equal_p (DR_REF (a), DR_REF (b), 0))
     613                 :             :     return true;
     614                 :             : 
     615                 :          58 :   if (!same_data_refs_base_objects (a, b))
     616                 :             :     return false;
     617                 :             : 
     618                 :         130 :   for (i = offset; i < DR_NUM_DIMENSIONS (a); i++)
     619                 :          26 :     if (!eq_evolutions_p (DR_ACCESS_FN (a, i), DR_ACCESS_FN (b, i)))
     620                 :             :       return false;
     621                 :             : 
     622                 :             :   return true;
     623                 :             : }
     624                 :             : 
     625                 :             : /* Returns true when all the dependences are computable.  */
     626                 :             : 
     627                 :             : inline bool
     628                 :             : known_dependences_p (vec<ddr_p> dependence_relations)
     629                 :             : {
     630                 :             :   ddr_p ddr;
     631                 :             :   unsigned int i;
     632                 :             : 
     633                 :             :   FOR_EACH_VEC_ELT (dependence_relations, i, ddr)
     634                 :             :     if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
     635                 :             :       return false;
     636                 :             : 
     637                 :             :   return true;
     638                 :             : }
     639                 :             : 
     640                 :             : /* Returns the dependence level for a vector DIST of size LENGTH.
     641                 :             :    LEVEL = 0 means a lexicographic dependence, i.e. a dependence due
     642                 :             :    to the sequence of statements, not carried by any loop.  */
     643                 :             : 
     644                 :             : inline unsigned
     645                 :         147 : dependence_level (lambda_vector dist_vect, int length)
     646                 :             : {
     647                 :         147 :   int i;
     648                 :             : 
     649                 :        1116 :   for (i = 0; i < length; i++)
     650                 :         850 :     if (dist_vect[i] != 0)
     651                 :         449 :       return i + 1;
     652                 :             : 
     653                 :             :   return 0;
     654                 :             : }
     655                 :             : 
     656                 :             : /* Return the dependence level for the DDR relation.  */
     657                 :             : 
     658                 :             : inline unsigned
     659                 :             : ddr_dependence_level (ddr_p ddr)
     660                 :             : {
     661                 :             :   unsigned vector;
     662                 :             :   unsigned level = 0;
     663                 :             : 
     664                 :             :   if (DDR_DIST_VECTS (ddr).exists ())
     665                 :             :     level = dependence_level (DDR_DIST_VECT (ddr, 0), DDR_NB_LOOPS (ddr));
     666                 :             : 
     667                 :             :   for (vector = 1; vector < DDR_NUM_DIST_VECTS (ddr); vector++)
     668                 :             :     level = MIN (level, dependence_level (DDR_DIST_VECT (ddr, vector),
     669                 :             :                                           DDR_NB_LOOPS (ddr)));
     670                 :             :   return level;
     671                 :             : }
     672                 :             : 
     673                 :             : /* Return the index of the variable VAR in the LOOP_NEST array.  */
     674                 :             : 
     675                 :             : inline int
     676                 :      134791 : index_in_loop_nest (int var, const vec<loop_p> &loop_nest)
     677                 :             : {
     678                 :      134791 :   class loop *loopi;
     679                 :      134791 :   int var_index;
     680                 :             : 
     681                 :      140426 :   for (var_index = 0; loop_nest.iterate (var_index, &loopi); var_index++)
     682                 :      140426 :     if (loopi->num == var)
     683                 :      134791 :       return var_index;
     684                 :             : 
     685                 :           0 :   gcc_unreachable ();
     686                 :             : }
     687                 :             : 
     688                 :             : /* Returns true when the data reference DR the form "A[i] = ..."
     689                 :             :    with a stride equal to its unit type size.  */
     690                 :             : 
     691                 :             : inline bool
     692                 :             : adjacent_dr_p (struct data_reference *dr)
     693                 :             : {
     694                 :             :   /* If this is a bitfield store bail out.  */
     695                 :             :   if (TREE_CODE (DR_REF (dr)) == COMPONENT_REF
     696                 :             :       && DECL_BIT_FIELD (TREE_OPERAND (DR_REF (dr), 1)))
     697                 :             :     return false;
     698                 :             : 
     699                 :             :   if (!DR_STEP (dr)
     700                 :             :       || TREE_CODE (DR_STEP (dr)) != INTEGER_CST)
     701                 :             :     return false;
     702                 :             : 
     703                 :             :   return tree_int_cst_equal (fold_unary (ABS_EXPR, TREE_TYPE (DR_STEP (dr)),
     704                 :             :                                          DR_STEP (dr)),
     705                 :             :                              TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr))));
     706                 :             : }
     707                 :             : 
     708                 :             : void split_constant_offset (tree , tree *, tree *);
     709                 :             : 
     710                 :             : /* Compute the greatest common divisor of a VECTOR of SIZE numbers.  */
     711                 :             : 
     712                 :             : inline lambda_int
     713                 :             : lambda_vector_gcd (lambda_vector vector, int size)
     714                 :             : {
     715                 :             :   int i;
     716                 :             :   lambda_int gcd1 = 0;
     717                 :             : 
     718                 :             :   if (size > 0)
     719                 :             :     {
     720                 :             :       gcd1 = vector[0];
     721                 :             :       for (i = 1; i < size; i++)
     722                 :             :         gcd1 = gcd (gcd1, vector[i]);
     723                 :             :     }
     724                 :             :   return gcd1;
     725                 :             : }
     726                 :             : 
     727                 :             : /* Allocate a new vector of given SIZE.  */
     728                 :             : 
     729                 :             : inline lambda_vector
     730                 :     1848976 : lambda_vector_new (int size)
     731                 :             : {
     732                 :             :   /* ???  We shouldn't abuse the GC allocator here.  */
     733                 :     1848976 :   return ggc_cleared_vec_alloc<lambda_int> (size);
     734                 :             : }
     735                 :             : 
     736                 :             : /* Clear out vector VEC1 of length SIZE.  */
     737                 :             : 
     738                 :             : inline void
     739                 :         678 : lambda_vector_clear (lambda_vector vec1, int size)
     740                 :             : {
     741                 :         678 :   memset (vec1, 0, size * sizeof (*vec1));
     742                 :           0 : }
     743                 :             : 
     744                 :             : /* Returns true when the vector V is lexicographically positive, in
     745                 :             :    other words, when the first nonzero element is positive.  */
     746                 :             : 
     747                 :             : inline bool
     748                 :       41508 : lambda_vector_lexico_pos (lambda_vector v,
     749                 :             :                           unsigned n)
     750                 :             : {
     751                 :       41508 :   unsigned i;
     752                 :       42343 :   for (i = 0; i < n; i++)
     753                 :             :     {
     754                 :       41642 :       if (v[i] == 0)
     755                 :         757 :         continue;
     756                 :       40885 :       if (v[i] < 0)
     757                 :             :         return false;
     758                 :             :       if (v[i] > 0)
     759                 :             :         return true;
     760                 :             :     }
     761                 :             :   return true;
     762                 :             : }
     763                 :             : 
     764                 :             : /* Return true if vector VEC1 of length SIZE is the zero vector.  */
     765                 :             : 
     766                 :             : inline bool
     767                 :       39686 : lambda_vector_zerop (lambda_vector vec1, int size)
     768                 :             : {
     769                 :       39686 :   int i;
     770                 :       84716 :   for (i = 0; i < size; i++)
     771                 :       49935 :     if (vec1[i] != 0)
     772                 :             :       return false;
     773                 :             :   return true;
     774                 :             : }
     775                 :             : 
     776                 :             : /* Allocate a matrix of M rows x  N cols.  */
     777                 :             : 
     778                 :             : inline lambda_matrix
     779                 :     2972468 : lambda_matrix_new (int m, int n, struct obstack *lambda_obstack)
     780                 :             : {
     781                 :     2972468 :   lambda_matrix mat;
     782                 :     2972468 :   int i;
     783                 :             : 
     784                 :     2972468 :   mat = XOBNEWVEC (lambda_obstack, lambda_vector, m);
     785                 :             : 
     786                 :     8916649 :   for (i = 0; i < m; i++)
     787                 :     5944181 :     mat[i] = XOBNEWVEC (lambda_obstack, lambda_int, n);
     788                 :             : 
     789                 :     2972468 :   return mat;
     790                 :             : }
     791                 :             : 
     792                 :             : #endif  /* GCC_TREE_DATA_REF_H  */
        

Generated by: LCOV version 2.0-1

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,rust,m2 --enable-host-shared. GCC test suite is run with the built compiler.