GCC Middle and Back End API Reference
graphite-scop-detection.c File Reference

Data Structures

struct  sd_region_p
struct  scopdet_info


typedef enum gbb_type gbb_type
typedef struct sd_region_p sd_region


enum  gbb_type {


static void make_close_phi_nodes_unique (basic_block)
static gbb_type get_bb_type ()
static void move_sd_regions ()
static bool graphite_can_represent_init ()
static bool graphite_can_represent_scev ()
static bool graphite_can_represent_expr (basic_block scop_entry, loop_p loop, tree expr)
static bool stmt_has_simple_data_refs_p (loop_p outermost_loop, gimple stmt)
static bool stmt_simple_for_scop_p (basic_block scop_entry, loop_p outermost_loop, gimple stmt, basic_block bb)
static gimple harmful_stmt_in_bb ()
static bool graphite_can_represent_loop ()
static struct scopdet_info build_scops_1 (basic_block, loop_p, vec< sd_region > *, loop_p)
static struct scopdet_info scopdet_basic_block_info (basic_block bb, loop_p outermost_loop, vec< sd_region > *scops, gbb_type type)
static bool bb_in_sd_region ()
static edge find_single_entry_edge ()
static edge find_single_exit_edge ()
static void create_single_entry_edge ()
static bool sd_region_without_exit ()
static void create_single_exit_edge ()
static void unmark_exit_edges ()
static void mark_exit_edges ()
static void create_sese_edges ()
static void build_graphite_scops (vec< sd_region > regions, vec< scop_p > *scops)
static bool contains_only_close_phi_nodes ()
static void print_graphite_scop_statistics ()
static void print_graphite_statistics ()
static void limit_scops ()
static bool same_close_phi_node ()
static void remove_duplicate_close_phi ()
static void make_close_phi_nodes_unique ()
static void canonicalize_loop_closed_ssa ()
static void canonicalize_loop_closed_ssa_form ()
void build_scops ()
static void dot_all_scops_1 ()
DEBUG_FUNCTION void dot_all_scops ()
DEBUG_FUNCTION void dot_scop ()

Typedef Documentation

typedef enum gbb_type gbb_type
   The type of the analyzed basic block.  
typedef struct sd_region_p sd_region
   A SCoP detection region, defined using bbs as borders.

   All control flow touching this region, comes in passing basic_block
   ENTRY and leaves passing basic_block EXIT.  By using bbs instead of
   edges for the borders we are able to represent also regions that do
   not have a single entry or exit edge.

   But as they have a single entry basic_block and a single exit
   basic_block, we are able to generate for every sd_region a single
   entry and exit edge.

   1   2
    \ /
     3  <- entry
    / \                 This region contains: {3, 4, 5, 6, 7, 8}
   5   6
   |   |
   7   8
    \ /
     9  <- exit  

Enumeration Type Documentation

enum gbb_type
   The type of the analyzed basic block.  

Function Documentation

static bool bb_in_sd_region ( )
   Checks if a bb is contained in REGION.  

Referenced by create_single_exit_edge(), and mark_exit_edges().

static void build_graphite_scops ( vec< sd_region regions,
vec< scop_p > *  scops 
   Create graphite SCoPs from an array of scop detection REGIONS.  
         Are there overlapping SCoPs?  

References basic_block_def::count.

Referenced by print_graphite_scop_statistics().

void build_scops ( )
   Find Static Control Parts (SCoP) in the current function and pushes
   them to SCOPS.  
static struct scopdet_info build_scops_1 ( basic_block  current,
loop_p  outermost_loop,
vec< sd_region > *  scops,
loop_p  loop 
   Starting from CURRENT we walk the dominance tree and add new sd_regions to
   SCOPS. The analyse if a sd_region can be handled is based on the value
   of OUTERMOST_LOOP. Only loops inside OUTERMOST loops may change.  LOOP
   is the loop in which CURRENT is handled.

   TODO: These functions got a little bit big. They definitely should be cleaned
     Initialize result.  
     Loop over the dominance tree.  If we meet a difficult bb, close
     the current SCoP.  Loop and condition header start a new layer,
     and can only be added if all bbs in deeper layers are simple.  
     Try to close open_scop, if we are still in an open SCoP.  
static void canonicalize_loop_closed_ssa ( )
   Transforms LOOP to the canonical loop closed SSA form.  
     The code above does not properly handle changes in the post dominance
     information (yet).  

References rewrite_into_loop_closed_ssa(), update_ssa(), and verify_loop_closed_ssa().

static void canonicalize_loop_closed_ssa_form ( )

Converts the current loop closed SSA form to a canonical form expected by the Graphite code generation.

The loop closed SSA form has the following invariant: a variable defined in a loop that is used outside the loop appears only in the phi nodes in the destination of the loop exit. These phi nodes are called close phi nodes.

The canonical loop closed SSA form contains the extra invariants:

  • when the loop contains only one exit, the close phi nodes contain only one argument. That implies that the basic block that contains the close phi nodes has only one predecessor, that is a basic block in the loop.
  • the basic block containing the close phi nodes does not contain other statements.
  • there exist only one phi node per definition in the loop.
static bool contains_only_close_phi_nodes ( )
   Returns true when BB contains only close phi nodes.  

References print_graphite_scop_statistics().

Referenced by print_graphite_scop_statistics().

static void create_sese_edges ( )
   Create for all scop regions a single entry and a single exit edge.  
       Don't handle multiple edges exiting the function.  

References gsi_end_p(), gsi_next(), gsi_start_bb(), and gsi_stmt().

Referenced by print_graphite_scop_statistics().

static void create_single_entry_edge ( )
   Create a single entry edge for REGION.  
     There are multiple predecessors for bb_3

  |  1  2
  |  | /
  |  |/
  |  3  <- entry
  |  |\
  |  | |
  |  4 ^
  |  | |
  |  |/
  |  5

  There are two edges (1->3, 2->3), that point from outside into the region,
  and another one (5->3), a loop latch, lead to bb_3.

  We split bb_3.

  |  1  2
  |  | /
  |  |/
  |  |\     (3.0 -> 3.1) = single entry edge
  |3.1 |        <- entry
  |  | |
  |  | |
  |  4 ^
  |  | |
  |  |/
  |  5

  If the loop is part of the SCoP, we have to redirect the loop latches.

  |  1  2
  |  | /
  |  |/
  |  |      (3.0 -> 3.1) = entry edge
  |3.1          <- entry
  |  |\
  |  | |
  |  4 ^
  |  | |
  |  |/
  |  5  
       This case is never executed, as the loop headers seem always to have a
       single edge pointing from outside into the loop.  

References edge_def::dest, sd_region_p::entry, and split_block_after_labels().

static void create_single_exit_edge ( )
   Create a single exit edge for REGION.  
     We create a forwarder bb (5) for all edges leaving this region
     (3->5, 4->5).  All other edges leading to the same bb, are moved
     to a new bb (6).  If these edges where part of another region (2->5)
     we update the region->exit pointer, of this region.

     To identify which edge belongs to which region we depend on the e->aux
     pointer in every edge.  It points to the region of the edge or to NULL,
     if the edge is not part of any region.

     1 2 3 4    1->5 no region,                 2->5 region->exit = 5,
      \| |/     3->5 region->exit = NULL,       4->5 region->exit = NULL
        5       <- exit

     changes to

     1 2 3 4    1->6 no region,                         2->6 region->exit = 6,
     | | \/     3->5 no region,                         4->5 no region,
     | |  5
      \| /      5->6 region->exit = 6

     Now there is only a single exit edge (5->6).  
     Unmark the edges, that are no longer exit edges.  
     Mark the new exit edge.  
     Update the exit bb of all regions, where exit edges lead to

References edge_def::aux, bb_in_sd_region(), sd_region_p::exit, basic_block_def::preds, and edge_def::src.

DEBUG_FUNCTION void dot_all_scops ( )
   Display all SCoPs using dotty.  
     When debugging, enable the following code.  This cannot be used
     in production compilers because it calls "system".  
static void dot_all_scops_1 ( )
   Pretty print to FILE all the SCoPs in DOT format and mark them with
   different colors.  If there are not enough colors, paint the
   remaining SCoPs in gray.

   Special nodes:
   - "*" after the node number denotes the entry of a SCoP,
   - "#" after the node number denotes the exit of a SCoP,
   - "()" around the node number denotes the entry or the
     exit nodes of the SCOP.  These are not part of SCoP.  
     Disable debugging while printing graph.  
         Use HTML for every bb label.  So we are able to print bbs
         which are part of two different SCoPs, with two different
         background colors.  
         Select color for SCoP.  
     Enable debugging again.  
DEBUG_FUNCTION void dot_scop ( )
   Display all SCoPs using dotty.  
     When debugging, enable the following code.  This cannot be used
     in production compilers because it calls "system".  
static edge find_single_entry_edge ( )
   Returns the single entry edge of REGION, if it does not exits NULL.  

Referenced by unmark_exit_edges().

static edge find_single_exit_edge ( )
   Returns the single exit edge of REGION, if it does not exits NULL.  

Referenced by unmark_exit_edges().

static gbb_type get_bb_type ( )
   Detect the type of BB.  Loop headers are only marked, if they are
   new.  This means their loop_father is different to LAST_LOOP.
   Otherwise they are treated like any other bb and their type can be
   any other type.  
     Check, if we entry into a new loop. 


static bool graphite_can_represent_expr ( basic_block  scop_entry,
loop_p  loop,
tree  expr 
   Return true when EXPR can be represented in the polyhedral model.

   This means an expression can be represented, if it is linear with
   respect to the loops and the strides are non parametric.
   LOOP is the place where the expr will be evaluated.  SCOP_ENTRY defines the
   entry of the region we analyse.  

References graphite_find_data_references_in_stmt(), loop_containing_stmt(), loop_outer(), and vNULL.

Referenced by stmt_simple_for_scop_p().

static bool graphite_can_represent_init ( )
   Something like "n * m" is not allowed.  
static bool graphite_can_represent_loop ( )
   Return true if LOOP can be represented in the polyhedral
   representation.  This is evaluated taking SCOP_ENTRY and
   OUTERMOST_LOOP in mind.  
     FIXME: For the moment, graphite cannot be used on loops that
     iterate using induction variables that wrap.  
static bool graphite_can_represent_scev ( )
   Return true when SCEV can be represented in the polyhedral model.

   An expression can be represented, if it can be expressed as an
   affine expression.  For loops (i, j) and parameters (m, n) all
   affine expressions are of the form:

   x1 * i + x2 * j + x3 * m + x4 * n + x5 * 1 where x1..x5 element of Z

   1 i + 20 j + (-2) m + 25

   Something like "i * n" or "n * m" is not allowed.  
         Check for constant strides.  With a non constant stride of
         'n' we would have a value of 'iv * n'.  Also check that the
         initial value can represented: for example 'n * m' cannot be
     Only affine functions can be represented.  
static gimple harmful_stmt_in_bb ( )
   Returns the statement of BB that contains a harmful operation: that
   can be a function call with side effects, the induction variables
   are not linear with respect to SCOP_ENTRY, etc.  The current open
   scop should end before this statement.  The evaluation is limited using
   OUTERMOST_LOOP as outermost loop that may change.  
static void limit_scops ( )
   We limit all SCoPs to SCoPs, that are completely surrounded by a loop.


   for (i      |
     {         |
       for (j  |  SCoP 1
       for (k  |
     }         |

   * SCoP frontier, as this line is not surrounded by any loop. *

   for (l      |  SCoP 2

   This is necessary as scalar evolution and parameter detection need a
   outermost loop to initialize parameters correctly.

   TODO: FIX scalar evolution and parameter detection to allow more flexible
         SCoP frontiers.  
               This is a hack on top of the limit_scops hack.  The
               limit_scops hack should disappear all together.  

References gimple_phi_num_args(), gsi_end_p(), gsi_next(), gsi_start_phis(), gsi_stmt(), remove_duplicate_close_phi(), and same_close_phi_node().

static void make_close_phi_nodes_unique ( basic_block  )

Detection of Static Control Parts (SCoP) for Graphite. Copyright (C) 2009-2013 Free Software Foundation, Inc. Contributed by Sebastian Pop sebas.nosp@m.tian.nosp@m..pop@.nosp@m.amd..nosp@m.com and Tobias Grosser gross.nosp@m.er@f.nosp@m.im.un.nosp@m.i-pa.nosp@m.ssau..nosp@m.de.

This file is part of GCC.

GCC is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version.

GCC is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with GCC; see the file COPYING3. If not see http://www.gnu.org/licenses/.

   Forward declarations.  

Referenced by same_close_phi_node().

static void make_close_phi_nodes_unique ( )
   Removes all the close phi duplicates from BB.  
         At this point, PHI should be a close phi in normal form.  
         Iterate over the next phis and remove duplicates.  
static void mark_exit_edges ( )
   Mark the exit edges of all REGIONS.
   See comment in "create_single_exit_edge". 

References bb_in_sd_region(), and sd_region_p::entry.

static void move_sd_regions ( )
   Moves the scops from SOURCE to TARGET and clean up SOURCE.  
static void print_graphite_statistics ( )
   Print statistics for SCOPS to FILE.  

References gimple_phi_arg_def(), and operand_equal_p().

static void remove_duplicate_close_phi ( )
   Remove the close phi node at GSI and replace its rhs with the rhs
   of PHI.  
         It is possible that we just created a duplicate close-phi
         for an already-processed containing loop.  Check for this
         case and clean it up.  

Referenced by limit_scops().

static bool same_close_phi_node ( )
   Returns true when P1 and P2 are close phis with the same

References make_close_phi_nodes_unique(), split_block_after_labels(), and edge_def::src.

Referenced by limit_scops().

static struct scopdet_info scopdet_basic_block_info ( basic_block  bb,
loop_p  outermost_loop,
vec< sd_region > *  scops,
gbb_type  type 
   Calculates BB infos. If bb is difficult we add valid SCoPs dominated by BB
   to SCOPS.  TYPE is the gbb_type of BB.  
     XXX: ENTRY_BLOCK_PTR could be optimized in later steps.  
         Mark bbs terminating a SESE region difficult, if they start
         a condition.  
           Try again with another loop level.  
               If we do not dominate result.next, remove it.  It's either
               the EXIT_BLOCK_PTR, or another bb dominates it and will
               call the scop detection for this bb.  
           XXX: For now we just do not join loops with multiple exits.  If the
           exits lead to the same bb it may be possible to join the loop.  
           Scan the code dominated by this loop.  This means all bbs, that are
           are dominated by a bb in this loop, but are not part of this loop.

           The easiest case:
             - The loop exit destination is dominated by the exit sources.

           TODO: We miss here the more complex cases:
                  - The exit destinations are dominated by another bb inside
                    the loop.
                  - The loop dominates bbs, that are not exit destinations.  
                 Pass loop_outer to recognize e->dest as loop header in
           First check the successors of BB, and check if it is
           possible to join the different branches.  
               Ignore loop exits.  They will be handled after the loop
               Do not follow edges that lead to the end of the
               conditions block.  For example, in

               |   0
               |  /|\
               | 1 2 |
               | | | |
               | 3 4 |
               |  \|/
               |   6

               the edge from 0 => 6.  Only check if all paths lead to
               the same node 6.  
                   Check, if edge leads directly to the end of this
               Checks, if all branches end at the same point.
               If that is true, the condition stays joinable.
               Have a look at the example above.  
           Join the branches of the condition if possible.  
               Only return a next pointer if we dominate this pointer.
               Otherwise it will be handled by the bb dominating it.  
           Scan remaining bbs dominated by BB.  
               Ignore loop exits: they will be handled after the loop body.  
               Ignore the bbs processed above.  
static bool sd_region_without_exit ( )
   Check if the sd_region, mentioned in EDGE, has no exit bb.  
static bool stmt_has_simple_data_refs_p ( loop_p  outermost_loop,
gimple  stmt 
   Return true if the data references of STMT can be represented by
static bool stmt_simple_for_scop_p ( basic_block  scop_entry,
loop_p  outermost_loop,
gimple  stmt,
basic_block  bb 
   Return true only when STMT is simple enough for being handled by
   Graphite.  This depends on SCOP_ENTRY, as the parameters are
   initialized relatively to this basic block, the linear functions
   are initialized to OUTERMOST_LOOP and BB is the place where we try
   to evaluate the STMT.  
     GIMPLE_ASM and GIMPLE_CALL may embed arbitrary side effects.
     Calls have side-effects, except those to const or pure
           We can handle all binary comparisons.  Inequalities are
           also supported as they can be represented with union of
                 We can not handle REAL_TYPE. Failed for pr39260.  
         These nodes cut a new scope.  

References gimple_cond_code(), and graphite_can_represent_expr().

static void unmark_exit_edges ( )
   Unmark the exit edges of all REGIONS.
   See comment in "create_single_exit_edge". 

References find_single_entry_edge(), find_single_exit_edge(), new_scop(), and new_sese().