GCC Middle and Back End API Reference
Data Structures | Typedefs | Enumerations | Functions | Variables
tree-loop-distribution.c File Reference

Data Structures

struct  partition_s

Typedefs

typedef struct partition_s * partition_t

Enumerations

enum  partition_kind { PKIND_NORMAL, PKIND_REDUCTION, PKIND_MEMSET, PKIND_MEMCPY }

Functions

static partition_t partition_alloc ()
static void partition_free ()
static bool partition_builtin_p ()
static bool partition_has_writes ()
static bool ssa_name_has_uses_outside_loop_p ()
static bool stmt_has_scalar_dependences_outside_loop ()
static struct loop * copy_loop_before ()
static void create_bb_after_loop ()
static void generate_loops_for_partition (struct loop *loop, partition_t partition, bool copy_p)
static tree build_size_arg_loc ()
static tree build_addr_arg_loc ()
static int const_with_all_bytes_same ()
static void generate_memset_builtin ()
static void generate_memcpy_builtin ()
static void destroy_loop ()
static void generate_code_for_partition (struct loop *loop, partition_t partition, bool copy_p)
static bool rdg_cannot_recompute_vertex_p ()
static bool already_processed_vertex_p ()
static struct graph_edge * has_anti_dependence ()
static bool predecessor_has_mem_write ()
static void mark_nodes_having_upstream_mem_writes ()
static bool has_upstream_mem_writes ()
static void rdg_flag_vertex_and_dependent (struct graph *, int, partition_t, bitmap, bitmap)
static void rdg_flag_uses (struct graph *rdg, int u, partition_t partition, bitmap loops, bitmap processed)
static void rdg_flag_vertex ()
static void collect_condition_stmts ()
static void rdg_flag_loop_exits (struct graph *rdg, bitmap loops, partition_t partition, bitmap processed)
static partition_t build_rdg_partition_for_component ()
static void free_rdg_components ()
static void rdg_build_components (struct graph *rdg, vec< int > starting_vertices, vec< rdgc > *components)
static void classify_partition ()
static tree ref_base_address ()
static bool similar_memory_accesses (struct graph *rdg, partition_t partition1, partition_t partition2)
static void rdg_build_partitions (struct graph *rdg, vec< rdgc > components, vec< int > *other_stores, vec< partition_t > *partitions, bitmap processed)
static void dump_rdg_partitions ()
void debug_rdg_partitions (vec< partition_t >)
DEBUG_FUNCTION void debug_rdg_partitions ()
static int number_of_rw_in_rdg ()
static int number_of_rw_in_partition ()
static bool partition_contains_all_rw (struct graph *rdg, vec< partition_t > partitions)
static int ldist_gen (struct loop *loop, struct graph *rdg, vec< int > starting_vertices)
static int distribute_loop ()
static unsigned int tree_loop_distribution ()
static bool gate_tree_loop_distribution ()
gimple_opt_pass * make_pass_loop_distribution ()

Variables

static bitmap remaining_stmts
static bitmap upstream_mem_writes

Typedef Documentation

typedef struct partition_s * partition_t

Enumeration Type Documentation

enum partition_kind 
@verbatim Loop distribution.

Copyright (C) 2006-2013 Free Software Foundation, Inc. Contributed by Georges-Andre Silber Georg.nosp@m.es-A.nosp@m.ndre..nosp@m.Silb.nosp@m.er@en.nosp@m.smp..nosp@m.fr and Sebastian Pop sebas.nosp@m.tian.nosp@m..pop@.nosp@m.amd..nosp@m.com.

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/. 

This pass performs loop distribution: for example, the loop

   |DO I = 2, N
   |    A(I) = B(I) + C
   |    D(I) = A(I-1)*E
   |ENDDO

   is transformed to

   |DOALL I = 2, N
   |   A(I) = B(I) + C
   |ENDDO
   |
   |DOALL I = 2, N
   |   D(I) = A(I-1)*E
   |ENDDO

   This pass uses an RDG, Reduced Dependence Graph built on top of the
   data dependence relations.  The RDG is then topologically sorted to
   obtain a map of information producers/consumers based on which it
   generates the new loops.
Enumerator:
PKIND_NORMAL 
PKIND_REDUCTION 
PKIND_MEMSET 
PKIND_MEMCPY 

Function Documentation

static bool already_processed_vertex_p ( )
inlinestatic 
Returns true when the vertex V has already been generated in the
   current partition (V is in PROCESSED), or when V belongs to another
   partition and cannot be recomputed (V is not in REMAINING_STMTS).

References bitmap_bit_p().

Referenced by build_rdg_partition_for_component(), rdg_flag_loop_exits(), rdg_flag_uses(), and rdg_flag_vertex_and_dependent().

static tree build_addr_arg_loc ( )
static 
Build an address argument for a memory operation call.

References DR_BASE_ADDRESS, DR_INIT, DR_OFFSET, DR_REF, DR_STEP, fold_build_pointer_plus_loc(), fold_convert_loc(), size_binop_loc(), and tree_int_cst_sgn().

Referenced by generate_memcpy_builtin(), and generate_memset_builtin().

static partition_t build_rdg_partition_for_component ( )
static 
Returns a bitmap in which all the statements needed for computing
   the strongly connected component C of the RDG are flagged, also
   including the loop exit conditions.

References already_processed_vertex_p(), partition_alloc(), processed, rdg_flag_loop_exits(), rdg_flag_vertex_and_dependent(), and rdg_component::vertices.

Referenced by rdg_build_partitions().

static tree build_size_arg_loc ( )
static 
Build the size argument for a memory operation call.

References DR_REF, and fold_convert_loc().

Referenced by generate_memcpy_builtin(), and generate_memset_builtin().

static void classify_partition ( )
static 
Classifies the builtin kind we can generate for PARTITION of RDG and LOOP.
   For the moment we detect only the memset zero pattern.

References adjacent_dr_p(), chrec_dont_know, chrec_known, compute_affine_dependence(), const_with_all_bytes_same(), DDR_ARE_DEPENDENT, DDR_DIST_VECTS, DDR_LOOP_NEST, DDR_NUM_DIST_VECTS, DDR_REVERSED_P, DR_IS_READ, DR_STEP, DR_STMT, dump_file, dump_flags, flow_bb_inside_loop_p(), free_dependence_relation(), gimple_assign_lhs(), gimple_assign_rhs1(), gimple_assign_single_p(), gimple_has_volatile_ops(), gimple_vuse(), index_in_loop_nest(), initialize_data_dependence_relation(), partition_s::kind, partition_s::main_dr, loop::num, number_of_exit_cond_executions(), operand_equal_p(), PKIND_MEMCPY, PKIND_MEMSET, PKIND_NORMAL, PKIND_REDUCTION, RDG_DATAREFS, RDG_STMT, partition_s::secondary_dr, stmt_has_scalar_dependences_outside_loop(), partition_s::stmts, and vNULL.

Referenced by ldist_gen().

static void collect_condition_stmts ( )
static 
Initialize CONDS with all the condition statements from the basic
   blocks of LOOP.

References loop::exits, get_loop_exit_edges(), last_stmt(), and edge_def::src.

Referenced by rdg_flag_loop_exits().

static int const_with_all_bytes_same ( )
static 
If VAL memory representation contains the same value in all bytes,
   return that value, otherwise return -1.
   E.g. for 0x24242424 return 0x24, for IEEE double
   747708026454360457216.0 return 0x44, etc.

References integer_zerop(), len, native_encode_expr(), and real_zerop().

Referenced by classify_partition(), and generate_memset_builtin().

static struct loop* copy_loop_before ( )
staticread 
Return a copy of LOOP placed before LOOP.

References delete_update_ssa(), free_original_copy_tables(), initialize_original_copy_tables(), loop_preheader_edge(), and slpeel_tree_duplicate_loop_to_edge_cfg().

Referenced by generate_loops_for_partition().

static void create_bb_after_loop ( )
static 
Creates an empty basic block after LOOP.

References single_exit(), and split_edge().

Referenced by generate_loops_for_partition().

void debug_rdg_partitions ( vec< partition_t >  ) 
Debug PARTITIONS.
DEBUG_FUNCTION void debug_rdg_partitions ( )

References dump_rdg_partitions().

static void destroy_loop ( )
static 
Remove and destroy the loop LOOP.

References cancel_loop_tree(), CDI_DOMINATORS, delete_basic_block(), edge_def::dest, edge_def::flags, free(), get_loop_body_in_dom_order(), gimple_phi_result(), gimple_vdef(), gsi_end_p(), gsi_next(), gsi_start_bb(), gsi_start_phis(), gsi_stmt(), loop_preheader_edge(), mark_virtual_operand_for_renaming(), mark_virtual_phi_result_for_renaming(), loop::num_nodes, recompute_dominator(), redirect_edge_pred(), rescan_loop_exit(), set_immediate_dominator(), single_exit(), edge_def::src, and virtual_operand_p().

Referenced by generate_code_for_partition().

static int distribute_loop ( )
static 
Distributes the code from LOOP in such a way that producer
   statements are placed before consumer statements.  When STMTS is
   NULL, performs the maximal distribution, if STMTS is not NULL,
   tries to separate only these statements from the LOOP's body.
   Returns the number of distributed loops.

References build_rdg(), dump_file, dump_flags, dump_rdg(), free_data_refs(), free_dependence_relations(), free_rdg(), ldist_gen(), loop::num, rdg_vertex_for_stmt(), and graph::vertices.

Referenced by tree_loop_distribution().

static void dump_rdg_partitions ( )
static 
Dump to FILE the PARTITIONS.

References debug_bitmap_file(), and partition_s::stmts.

Referenced by debug_rdg_partitions(), and ldist_gen().

static void free_rdg_components ( )
static 
Free memory for COMPONENTS.

References free(), and rdg_component::vertices.

Referenced by ldist_gen(), and rdg_build_partitions().

static bool gate_tree_loop_distribution ( )
static
static void generate_code_for_partition ( struct loop *  loop,
partition_t  partition,
bool  copy_p 
)
static 
Generates code for PARTITION.

References destroy_loop(), generate_loops_for_partition(), generate_memcpy_builtin(), generate_memset_builtin(), partition_s::kind, PKIND_MEMCPY, PKIND_MEMSET, PKIND_NORMAL, and PKIND_REDUCTION.

Referenced by ldist_gen().

static void generate_loops_for_partition ( struct loop *  loop,
partition_t  partition,
bool  copy_p 
)
static 
Generate code for PARTITION from the code in LOOP.  The loop is
   copied when COPY_P is true.  All the statements not flagged in the
   PARTITION bitmap are removed from the loop or from its copy.  The
   statements are indexed in sequence inside a basic block, and the
   basic blocks of a loop are taken in dom order.

References bitmap_bit_p(), copy_loop_before(), CP_SIMPLE_PREHEADERS, create_bb_after_loop(), create_preheader(), free(), get_loop_body_in_dom_order(), gimple_phi_result(), gsi_end_p(), gsi_next(), gsi_remove(), gsi_start_bb(), gsi_start_phis(), gsi_stmt(), is_gimple_debug(), mark_virtual_phi_result_for_renaming(), loop::num_nodes, release_defs(), remove_phi_node(), reset_debug_uses(), partition_s::stmts, unlink_stmt_vdef(), and virtual_operand_p().

Referenced by generate_code_for_partition().

static void generate_memcpy_builtin ( )
static 
Generate a call to memcpy for PARTITION in LOOP.

References build_addr_arg_loc(), build_size_arg_loc(), builtin_decl_implicit(), DR_STMT, dump_file, dump_flags, force_gimple_operand_gsi(), gimple_build_call(), gimple_location(), GSI_CONTINUE_LINKING, gsi_insert_after(), gsi_last_bb(), loop::latch, loop_preheader_edge(), partition_s::main_dr, number_of_exit_cond_executions(), number_of_latch_executions(), ptr_derefs_may_alias_p(), and partition_s::secondary_dr.

Referenced by generate_code_for_partition().

static void generate_memset_builtin ( )
static 
Generate a call to memset for PARTITION in LOOP.

References build_addr_arg_loc(), build_int_cst(), build_size_arg_loc(), builtin_decl_implicit(), const_with_all_bytes_same(), DR_STMT, dump_file, dump_flags, force_gimple_operand_gsi(), gimple_assign_rhs1(), gimple_build_assign_with_ops(), gimple_build_call(), gimple_location(), GSI_CONTINUE_LINKING, gsi_insert_after(), gsi_last_bb(), loop::latch, loop_preheader_edge(), partition_s::main_dr, make_ssa_name(), number_of_exit_cond_executions(), number_of_latch_executions(), and useless_type_conversion_p().

Referenced by generate_code_for_partition().

static struct graph_edge* has_anti_dependence ( )
staticread 
Returns NULL when there is no anti-dependence among the successors
   of vertex V, otherwise returns the edge with the anti-dep.

References anti_dd, RDGE_TYPE, vertex::succ, and graph_edge::succ_next.

Referenced by mark_nodes_having_upstream_mem_writes(), and rdg_flag_uses().

static bool has_upstream_mem_writes ( )
static 
Returns true when vertex u has a memory write node as a predecessor
   in RDG.

References bitmap_bit_p().

Referenced by rdg_flag_uses().

static int ldist_gen ( struct loop *  loop,
struct graph *  rdg,
vec< int >  starting_vertices 
)
static 
Generate code from STARTING_VERTICES in RDG.  Returns the number of
   distributed loops.

References bitmap_ior_into(), bitmap_set_bit(), classify_partition(), dump_bitmap(), dump_file, dump_flags, dump_rdg_partitions(), free_rdg_components(), generate_code_for_partition(), partition_s::kind, mark_nodes_having_upstream_mem_writes(), graph::n_vertices, partition_builtin_p(), partition_contains_all_rw(), partition_free(), PKIND_REDUCTION, processed, rdg_build_components(), rdg_build_partitions(), RDG_MEM_WRITE_STMT, similar_memory_accesses(), and partition_s::stmts.

Referenced by distribute_loop().

gimple_opt_pass* make_pass_loop_distribution ( )
static void mark_nodes_having_upstream_mem_writes ( )
static 
Initializes the upstream_mem_writes bitmap following the
   information from RDG.

References bitmap_bit_p(), bitmap_set_bit(), graphds_dfs(), has_anti_dependence(), graph::n_vertices, predecessor_has_mem_write(), RDG_MEM_WRITE_STMT, and graph::vertices.

Referenced by ldist_gen().

static int number_of_rw_in_partition ( )
static 
Returns the number of read and write operations in a PARTITION of
   the RDG.

References RDG_MEM_READS_STMT, RDG_MEM_WRITE_STMT, and partition_s::stmts.

Referenced by partition_contains_all_rw().

static int number_of_rw_in_rdg ( )
static 
Returns the number of read and write operations in the RDG.

References graph::n_vertices, RDG_MEM_READS_STMT, and RDG_MEM_WRITE_STMT.

Referenced by partition_contains_all_rw().

static partition_t partition_alloc ( )
static 
Allocate and initialize a partition from BITMAP.

References partition_s::has_writes, partition_s::kind, PKIND_NORMAL, and partition_s::stmts.

Referenced by build_rdg_partition_for_component(), and rdg_build_partitions().

static bool partition_builtin_p ( )
static 
Returns true if the partition can be generated as a builtin.

References partition_s::kind, and PKIND_REDUCTION.

Referenced by ldist_gen().

static bool partition_contains_all_rw ( struct graph *  rdg,
vec< partition_t >  partitions 
)
static 
Returns true when one of the PARTITIONS contains all the read or
   write operations of RDG.

References number_of_rw_in_partition(), and number_of_rw_in_rdg().

Referenced by ldist_gen().

static void partition_free ( )
static 
Free PARTITION.

References free(), and partition_s::stmts.

Referenced by ldist_gen(), and rdg_build_partitions().

static bool partition_has_writes ( )
static 
Returns true if the partition has an writes.

References partition_s::has_writes.

Referenced by rdg_build_partitions().

static bool predecessor_has_mem_write ( )
static 
Returns true when V has an anti-dependence edge among its successors.

References bitmap_bit_p(), vertex::pred, graph_edge::pred_next, RDG_MEM_WRITE_STMT, and graph_edge::src.

Referenced by mark_nodes_having_upstream_mem_writes().

static void rdg_build_components ( struct graph *  rdg,
vec< int >  starting_vertices,
vec< rdgc > *  components 
)
static 
Build the COMPONENTS vector with the strongly connected components
   of RDG in which the STARTING_VERTICES occur.

References bitmap_bit_p(), bitmap_set_bit(), vertex::component, free(), graphds_scc(), graph::n_vertices, rdg_component::num, graph::vertices, and rdg_component::vertices.

Referenced by ldist_gen(), and rdg_build_partitions().

static void rdg_build_partitions ( struct graph *  rdg,
vec< rdgc >  components,
vec< int > *  other_stores,
vec< partition_t > *  partitions,
bitmap  processed 
)
static 
Aggregate several components into a useful partition that is
   registered in the PARTITIONS vector.  Partitions will be
   distributed in different loops.

References bitmap_bit_p(), bitmap_count_bits(), bitmap_ior_into(), build_rdg_partition_for_component(), dump_bitmap(), dump_file, dump_flags, foo(), free_rdg_components(), partition_s::has_writes, graph::n_vertices, partition_alloc(), partition_free(), partition_has_writes(), rdg_build_components(), rdg_defs_used_in_other_loops_p(), partition_s::stmts, and rdg_component::vertices.

Referenced by ldist_gen().

static bool rdg_cannot_recompute_vertex_p ( )
static 
Returns true if the node V of RDG cannot be recomputed.

References RDG_MEM_WRITE_STMT.

Referenced by rdg_flag_vertex().

static void rdg_flag_loop_exits ( struct graph *  rdg,
bitmap  loops,
partition_t  partition,
bitmap  processed 
)
static 
Add to PARTITION all the exit condition statements for LOOPS
   together with all their dependent statements determined from
   RDG.

References already_processed_vertex_p(), bitmap_set_bit(), cfun, collect_condition_stmts(), get_loop(), rdg_flag_vertex_and_dependent(), and rdg_vertex_for_stmt().

Referenced by build_rdg_partition_for_component().

static void rdg_flag_uses ( struct graph *  rdg,
int  u,
partition_t  partition,
bitmap  loops,
bitmap  processed 
)
static 
Flag the uses of U stopping following the information from
   upstream_mem_writes.

References already_processed_vertex_p(), graph_edge::dest, gimple_assign_lhs(), gimple_vuse_op(), has_anti_dependence(), has_upstream_mem_writes(), is_gimple_assign(), is_gimple_reg(), rdg_flag_vertex_and_dependent(), rdg_vertex_for_stmt(), RDGV_STMT, and graph::vertices.

Referenced by rdg_flag_vertex_and_dependent().

static void rdg_flag_vertex ( )
static 
Flag V from RDG as part of PARTITION, and also flag its loop number
   in LOOPS.

References bitmap_clear_bit(), bitmap_set_bit(), partition_s::has_writes, loop_containing_stmt(), loop::num, rdg_cannot_recompute_vertex_p(), RDG_STMT, and partition_s::stmts.

Referenced by rdg_flag_vertex_and_dependent().

static void rdg_flag_vertex_and_dependent ( struct graph *  rdg,
int  v,
partition_t  partition,
bitmap  loops,
bitmap  processed 
)
static 
Flag in the bitmap PARTITION the vertex V and all its predecessors.
   Also flag their loop number in LOOPS.

References already_processed_vertex_p(), bitmap_set_bit(), graphds_dfs(), rdg_flag_uses(), and rdg_flag_vertex().

Referenced by build_rdg_partition_for_component(), rdg_flag_loop_exits(), and rdg_flag_uses().

static tree ref_base_address ( )
static 
For a data reference REF, return the declaration of its base
   address or NULL_TREE if the base is not determined.

References DR_BASE_ADDRESS.

Referenced by similar_memory_accesses().

static bool similar_memory_accesses ( struct graph *  rdg,
partition_t  partition1,
partition_t  partition2 
)
static 
Returns true when PARTITION1 and PARTITION2 have similar memory
   accesses in RDG.

References RDG_DATAREFS, RDG_MEM_READS_STMT, RDG_MEM_WRITE_STMT, ref_base_address(), and partition_s::stmts.

Referenced by ldist_gen().

static bool ssa_name_has_uses_outside_loop_p ( )
static 
Returns true when DEF is an SSA_NAME defined in LOOP and used after
   the LOOP.

References is_gimple_debug(), and loop_containing_stmt().

Referenced by stmt_has_scalar_dependences_outside_loop().

static bool stmt_has_scalar_dependences_outside_loop ( )
static 
Returns true when STMT defines a scalar variable used after the
   loop LOOP.

References gimple_phi_result(), and ssa_name_has_uses_outside_loop_p().

Referenced by classify_partition(), and tree_loop_distribution().

static unsigned int tree_loop_distribution ( )
static 
Distribute all loops in the current function.

References cfun, changed, distribute_loop(), dump_file, dump_flags, free(), get_loop_body_in_dom_order(), gimple_assign_lhs(), gimple_assign_single_p(), gimple_set_uid(), gsi_end_p(), gsi_next(), gsi_start_bb(), gsi_start_phis(), gsi_stmt(), is_gimple_reg(), LI_ONLY_INNERMOST, mark_virtual_operands_for_renaming(), loop::num, loop::num_nodes, optimize_loop_for_speed_p(), rewrite_into_loop_closed_ssa(), single_exit(), stmt_has_scalar_dependences_outside_loop(), verify_loop_structure(), and vNULL.

Variable Documentation

bitmap remaining_stmts
static 
If bit I is not set, it means that this node represents an
   operation that has already been performed, and that should not be
   performed again.  This is the subgraph of remaining important
   computations that is passed to the DFS algorithm for avoiding to
   include several times the same stores in different loops.
bitmap upstream_mem_writes
static 
A node of the RDG is marked in this bitmap when it has as a
   predecessor a node that writes to memory.