LCOV - code coverage report
Current view: top level - gcc - sese.h (source / functions) Hit Total Coverage
Test: gcc.info Lines: 34 34 100.0 %
Date: 2020-03-28 11:57:23 Functions: 5 5 100.0 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 0 -

           Branch data     Line data    Source code
       1                 :            : /* Single entry single exit control flow regions.
       2                 :            :    Copyright (C) 2008-2020 Free Software Foundation, Inc.
       3                 :            :    Contributed by Jan Sjodin <jan.sjodin@amd.com> and
       4                 :            :    Sebastian Pop <sebastian.pop@amd.com>.
       5                 :            : 
       6                 :            : This file is part of GCC.
       7                 :            : 
       8                 :            : GCC is free software; you can redistribute it and/or modify
       9                 :            : it under the terms of the GNU General Public License as published by
      10                 :            : the Free Software Foundation; either version 3, or (at your option)
      11                 :            : any later version.
      12                 :            : 
      13                 :            : GCC is distributed in the hope that it will be useful,
      14                 :            : but WITHOUT ANY WARRANTY; without even the implied warranty of
      15                 :            : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      16                 :            : GNU General Public License for more details.
      17                 :            : 
      18                 :            : You should have received a copy of the GNU General Public License
      19                 :            : along with GCC; see the file COPYING3.  If not see
      20                 :            : <http://www.gnu.org/licenses/>.  */
      21                 :            : 
      22                 :            : #ifndef GCC_SESE_H
      23                 :            : #define GCC_SESE_H
      24                 :            : 
      25                 :            : typedef struct ifsese_s *ifsese;
      26                 :            : 
      27                 :            : /* A Single Entry, Single Exit region is a part of the CFG delimited
      28                 :            :    by two edges.  */
      29                 :            : class sese_l
      30                 :            : {
      31                 :            : public:
      32                 :       1004 :   sese_l (edge e, edge x) : entry (e), exit (x) {}
      33                 :            : 
      34                 :      14936 :   operator bool () const { return entry && exit; }
      35                 :            : 
      36                 :            :   edge entry;
      37                 :            :   edge exit;
      38                 :            : };
      39                 :            : 
      40                 :            : void print_edge (FILE *file, const_edge e);
      41                 :            : void print_sese (FILE *file, const sese_l &s);
      42                 :            : void dump_edge (const_edge e);
      43                 :            : void dump_sese (const sese_l &);
      44                 :            : 
      45                 :            : /* Get the entry of an sese S.  */
      46                 :            : 
      47                 :            : static inline basic_block
      48                 :       2043 : get_entry_bb (sese_l &s)
      49                 :            : {
      50                 :       2043 :   return s.entry->dest;
      51                 :            : }
      52                 :            : 
      53                 :            : /* Get the exit of an sese S.  */
      54                 :            : 
      55                 :            : static inline basic_block
      56                 :       1434 : get_exit_bb (sese_l &s)
      57                 :            : {
      58                 :       1434 :   return s.exit->src;
      59                 :            : }
      60                 :            : 
      61                 :            : /* Returns the index of V where ELEM can be found. -1 Otherwise.  */
      62                 :            : template<typename T>
      63                 :            : int
      64                 :            : vec_find (const vec<T> &v, const T &elem)
      65                 :            : {
      66                 :            :   int i;
      67                 :            :   T t;
      68                 :            :   FOR_EACH_VEC_ELT (v, i, t)
      69                 :            :     if (elem == t)
      70                 :            :       return i;
      71                 :            :   return -1;
      72                 :            : }
      73                 :            : 
      74                 :            : /* A helper structure for bookkeeping information about a scop in graphite.  */
      75                 :            : typedef class sese_info_t
      76                 :            : {
      77                 :            : public:
      78                 :            :   /* The SESE region.  */
      79                 :            :   sese_l region;
      80                 :            : 
      81                 :            :   /* Liveout vars.  */
      82                 :            :   bitmap liveout;
      83                 :            : 
      84                 :            :   /* Liveout in debug stmts.  */
      85                 :            :   bitmap debug_liveout;
      86                 :            : 
      87                 :            :   /* Parameters used within the SCOP.  */
      88                 :            :   vec<tree> params;
      89                 :            : 
      90                 :            :   /* Maps an old name to a new decl.  */
      91                 :            :   hash_map<tree, tree> *rename_map;
      92                 :            : 
      93                 :            :   /* Basic blocks contained in this SESE.  */
      94                 :            :   vec<basic_block> bbs;
      95                 :            : 
      96                 :            :   /* The condition region generated for this sese.  */
      97                 :            :   ifsese if_region;
      98                 :            : 
      99                 :            : } *sese_info_p;
     100                 :            : 
     101                 :            : extern sese_info_p new_sese_info (edge, edge);
     102                 :            : extern void free_sese_info (sese_info_p);
     103                 :            : extern void sese_insert_phis_for_liveouts (sese_info_p, basic_block, edge, edge);
     104                 :            : extern class loop *outermost_loop_in_sese (sese_l &, basic_block);
     105                 :            : extern tree scalar_evolution_in_region (const sese_l &, loop_p, tree);
     106                 :            : extern bool scev_analyzable_p (tree, sese_l &);
     107                 :            : extern bool invariant_in_sese_p_rec (tree, const sese_l &, bool *);
     108                 :            : extern void sese_build_liveouts (sese_info_p);
     109                 :            : extern bool sese_trivially_empty_bb_p (basic_block);
     110                 :            : 
     111                 :            : /* The number of parameters in REGION. */
     112                 :            : 
     113                 :            : static inline unsigned
     114                 :        485 : sese_nb_params (sese_info_p region)
     115                 :            : {
     116                 :        485 :   return region->params.length ();
     117                 :            : }
     118                 :            : 
     119                 :            : /* Checks whether BB is contained in the region delimited by ENTRY and
     120                 :            :    EXIT blocks.  */
     121                 :            : 
     122                 :            : static inline bool
     123                 :     202054 : bb_in_region (const_basic_block bb, const_basic_block entry, const_basic_block exit)
     124                 :            : {
     125                 :     202054 :   return dominated_by_p (CDI_DOMINATORS, bb, entry)
     126                 :     205229 :          && !(dominated_by_p (CDI_DOMINATORS, bb, exit)
     127                 :       3175 :               && !dominated_by_p (CDI_DOMINATORS, entry, exit));
     128                 :            : }
     129                 :            : 
     130                 :            : /* Checks whether BB is contained in the region delimited by ENTRY and
     131                 :            :    EXIT blocks.  */
     132                 :            : 
     133                 :            : static inline bool
     134                 :      49514 : bb_in_sese_p (basic_block bb, const sese_l &r)
     135                 :            : {
     136                 :      19445 :   return bb_in_region (bb, r.entry->dest, r.exit->dest);
     137                 :            : }
     138                 :            : 
     139                 :            : /* Returns true when STMT is defined in REGION.  */
     140                 :            : 
     141                 :            : static inline bool
     142                 :      32173 : stmt_in_sese_p (gimple *stmt, const sese_l &r)
     143                 :            : {
     144                 :      32173 :   basic_block bb = gimple_bb (stmt);
     145                 :      32173 :   return bb && bb_in_sese_p (bb, r);
     146                 :            : }
     147                 :            : 
     148                 :            : /* Returns true when NAME is defined in REGION.  */
     149                 :            : 
     150                 :            : static inline bool
     151                 :      32173 : defined_in_sese_p (tree name, const sese_l &r)
     152                 :            : {
     153                 :      32173 :   return stmt_in_sese_p (SSA_NAME_DEF_STMT (name), r);
     154                 :            : }
     155                 :            : 
     156                 :            : /* Returns true when LOOP is in REGION.  */
     157                 :            : 
     158                 :            : static inline bool
     159                 :            : loop_in_sese_p (class loop *loop, const sese_l &region)
     160                 :            : {
     161                 :            :   return (bb_in_sese_p (loop->header, region)
     162                 :            :           && bb_in_sese_p (loop->latch, region));
     163                 :            : }
     164                 :            : 
     165                 :            : /* Returns the loop depth of LOOP in REGION.  The loop depth
     166                 :            :    is the same as the normal loop depth, but limited by a region.
     167                 :            : 
     168                 :            :    Example:
     169                 :            : 
     170                 :            :    loop_0
     171                 :            :      loop_1
     172                 :            :        {
     173                 :            :          S0
     174                 :            :             <- region start
     175                 :            :          S1
     176                 :            : 
     177                 :            :          loop_2
     178                 :            :            S2
     179                 :            : 
     180                 :            :          S3
     181                 :            :             <- region end
     182                 :            :        }
     183                 :            : 
     184                 :            :     loop_0 does not exist in the region -> invalid
     185                 :            :     loop_1 exists, but is not completely contained in the region -> depth 0
     186                 :            :     loop_2 is completely contained -> depth 1  */
     187                 :            : 
     188                 :            : static inline unsigned int
     189                 :       1653 : sese_loop_depth (const sese_l &region, loop_p loop)
     190                 :            : {
     191                 :       1653 :   unsigned int depth = 0;
     192                 :            : 
     193                 :       4373 :   while (loop_in_sese_p (loop, region))
     194                 :            :     {
     195                 :       2720 :       depth++;
     196                 :       2720 :       loop = loop_outer (loop);
     197                 :            :     }
     198                 :            : 
     199                 :       1653 :   return depth;
     200                 :            : }
     201                 :            : 
     202                 :            : /* A single entry single exit specialized for conditions.  */
     203                 :            : 
     204                 :            : typedef struct ifsese_s {
     205                 :            :   sese_info_p region;
     206                 :            :   sese_info_p true_region;
     207                 :            :   sese_info_p false_region;
     208                 :            : } *ifsese;
     209                 :            : 
     210                 :            : extern ifsese move_sese_in_condition (sese_info_p);
     211                 :            : extern void set_ifsese_condition (ifsese, tree);
     212                 :            : extern edge get_true_edge_from_guard_bb (basic_block);
     213                 :            : extern edge get_false_edge_from_guard_bb (basic_block);
     214                 :            : 
     215                 :            : static inline edge
     216                 :            : if_region_entry (ifsese if_region)
     217                 :            : {
     218                 :            :   return if_region->region->region.entry;
     219                 :            : }
     220                 :            : 
     221                 :            : static inline edge
     222                 :            : if_region_exit (ifsese if_region)
     223                 :            : {
     224                 :            :   return if_region->region->region.exit;
     225                 :            : }
     226                 :            : 
     227                 :            : static inline basic_block
     228                 :            : if_region_get_condition_block (ifsese if_region)
     229                 :            : {
     230                 :            :   return if_region_entry (if_region)->dest;
     231                 :            : }
     232                 :            : 
     233                 :            : typedef std::pair <gimple *, tree> scalar_use;
     234                 :            : 
     235                 :            : typedef struct gimple_poly_bb
     236                 :            : {
     237                 :            :   basic_block bb;
     238                 :            :   struct poly_bb *pbb;
     239                 :            : 
     240                 :            :   /* Lists containing the restrictions of the conditional statements
     241                 :            :      dominating this bb.  This bb can only be executed, if all conditions
     242                 :            :      are true.
     243                 :            : 
     244                 :            :      Example:
     245                 :            : 
     246                 :            :      for (i = 0; i <= 20; i++)
     247                 :            :      {
     248                 :            :        A
     249                 :            : 
     250                 :            :        if (2i <= 8)
     251                 :            :          B
     252                 :            :      }
     253                 :            : 
     254                 :            :      So for B there is an additional condition (2i <= 8).
     255                 :            : 
     256                 :            :      List of COND_EXPR and SWITCH_EXPR.  A COND_EXPR is true only if the
     257                 :            :      corresponding element in CONDITION_CASES is not NULL_TREE.  For a
     258                 :            :      SWITCH_EXPR the corresponding element in CONDITION_CASES is a
     259                 :            :      CASE_LABEL_EXPR.  */
     260                 :            :   vec<gimple *> conditions;
     261                 :            :   vec<gimple *> condition_cases;
     262                 :            :   vec<data_reference_p> data_refs;
     263                 :            :   vec<scalar_use> read_scalar_refs;
     264                 :            :   vec<tree> write_scalar_refs;
     265                 :            : } *gimple_poly_bb_p;
     266                 :            : 
     267                 :            : #define GBB_BB(GBB) (GBB)->bb
     268                 :            : #define GBB_PBB(GBB) (GBB)->pbb
     269                 :            : #define GBB_DATA_REFS(GBB) (GBB)->data_refs
     270                 :            : #define GBB_CONDITIONS(GBB) (GBB)->conditions
     271                 :            : #define GBB_CONDITION_CASES(GBB) (GBB)->condition_cases
     272                 :            : 
     273                 :            : /* Return the innermost loop that contains the basic block GBB.  */
     274                 :            : 
     275                 :            : static inline class loop *
     276                 :       6212 : gbb_loop (gimple_poly_bb_p gbb)
     277                 :            : {
     278                 :       4331 :   return GBB_BB (gbb)->loop_father;
     279                 :            : }
     280                 :            : 
     281                 :            : /* Returns the gimple loop, that corresponds to the loop_iterator_INDEX.
     282                 :            :    If there is no corresponding gimple loop, we return NULL.  */
     283                 :            : 
     284                 :            : static inline loop_p
     285                 :        706 : gbb_loop_at_index (gimple_poly_bb_p gbb, sese_l &region, int index)
     286                 :            : {
     287                 :        706 :   loop_p loop = gbb_loop (gbb);
     288                 :        706 :   int depth = sese_loop_depth (region, loop);
     289                 :            : 
     290                 :       1004 :   while (--depth > index)
     291                 :        298 :     loop = loop_outer (loop);
     292                 :            : 
     293                 :        706 :   gcc_assert (loop_in_sese_p (loop, region));
     294                 :            : 
     295                 :        706 :   return loop;
     296                 :            : }
     297                 :            : 
     298                 :            : /* The number of common loops in REGION for GBB1 and GBB2.  */
     299                 :            : 
     300                 :            : static inline int
     301                 :            : nb_common_loops (sese_l &region, gimple_poly_bb_p gbb1, gimple_poly_bb_p gbb2)
     302                 :            : {
     303                 :            :   loop_p l1 = gbb_loop (gbb1);
     304                 :            :   loop_p l2 = gbb_loop (gbb2);
     305                 :            :   loop_p common = find_common_loop (l1, l2);
     306                 :            : 
     307                 :            :   return sese_loop_depth (region, common);
     308                 :            : }
     309                 :            : 
     310                 :            : #endif

Generated by: LCOV version 1.0

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