LCOV - code coverage report
Current view: top level - gcc - tree-data-ref.h (source / functions) Coverage Total Hit
Test: gcc.info Lines: 96.6 % 58 56
Test Date: 2026-11-14 16:39:50 Functions: 100.0 % 5 5
Legend: Lines:     hit not hit

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

Generated by: LCOV version 2.5.0-beta

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.