diff options
| -rw-r--r-- | gcc/ChangeLog | 75 | ||||
| -rw-r--r-- | gcc/cfgloop.c | 110 | ||||
| -rw-r--r-- | gcc/cfgloop.h | 33 | ||||
| -rw-r--r-- | gcc/loop-unroll.c | 16 | ||||
| -rw-r--r-- | gcc/tree-flow-inline.h | 15 | ||||
| -rw-r--r-- | gcc/tree-flow.h | 112 | ||||
| -rw-r--r-- | gcc/tree-scalar-evolution.h | 3 | ||||
| -rw-r--r-- | gcc/tree-ssa-loop-ch.c | 3 | ||||
| -rw-r--r-- | gcc/tree-ssa-loop-im.c | 275 | ||||
| -rw-r--r-- | gcc/tree-ssa-loop-ivcanon.c | 200 | ||||
| -rw-r--r-- | gcc/tree-ssa-loop-ivopts.c | 27 | ||||
| -rw-r--r-- | gcc/tree-ssa-loop-ivopts.h | 36 | ||||
| -rw-r--r-- | gcc/tree-ssa-loop-manip.h | 49 | ||||
| -rw-r--r-- | gcc/tree-ssa-loop-niter.c | 116 | ||||
| -rw-r--r-- | gcc/tree-ssa-loop-niter.h | 46 | ||||
| -rw-r--r-- | gcc/tree-ssa-loop-prefetch.c | 57 | ||||
| -rw-r--r-- | gcc/tree-ssa-loop-unswitch.c | 57 | ||||
| -rw-r--r-- | gcc/tree-ssa-loop.c | 575 | ||||
| -rw-r--r-- | gcc/tree-ssa-loop.h | 85 |
19 files changed, 1034 insertions, 856 deletions
diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 95c490bcd36..92fc367e69a 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,78 @@ +2013-10-09 Andrew MacLeod <amacleod@redhat.com> + + * tree-flow.h: Move some protoypes. Include new tree-ssa-loop.h. + (struct affine_iv, struct tree_niter_desc): Move to tree-ssa-loop.h. + (enum move_pos): Move to tree-ssa-loop-im.h + * cfgloop.h: Move some prototypes. + (gcov_type_to_double_int): relocate from tree-ssa-loop.niter.c. + * tree-flow-inline.h (loop_containing_stmt): Move to tree-ssa-loop.h. + * tree-ssa-loop.h: New File. Include other tree-ssa-loop-*.h files. + (struct affine_iv, struct tree_niter_desc): Relocate from tree-flow.h. + (loop_containing_stmt): Relocate from tree-flow-inline.h. + * tree-ssa-loop-ch.c: (do_while_loop_p): Make static. + * tree-ssa-loop-im.c (for_each_index): Move to tree-ssa-loop.c. + (enum move_pos): Relocate here. + (lsm_tmp_name_add, gen_lsm_tmp_name, get_lsm_tmp_name): Move to + tree-ssa-loop.c. + (execute_sm_if_changed_flag_set): Change get_lsm_tmp_name call. + (tree_ssa_loop_im, gate_tree_ssa_loop_im, pass_data_lim, make_pass_lim): + Relocate here from tree-ssa-loop.c. + * tree-ssa-loop-ivcanon.c (tree_num_loop_insns): Move to + tree-ssa-loop.c. + (loop_edge_to_cancel, unloop_loops): Make static. + (tree_ssa_loop_ivcanon, gate_tree_ssa_loop_ivcanon, pass_data_iv_canon, + make_pass_iv_canon): Relocate from tree-ssa-loop.c. + (tree_complete_unroll, gate_tree_complete_unroll, + pass_data_complete_unroll, make_pass_complete_unroll): Relocate here. + (tree_complete_unroll_inner, gate_tree_complete_unroll_inner, + pass_data_complete_unrolli, make_pass_complete_unrolli): Relocate here. + * tree-ssa-loop-ivopts.c: Remove local prototypes. + (stmt_invariant_in_loop_p): Remove unused function. + * tree-ssa-loop-ivopts.h: New file. Add prototypes. + * tree-ssa-loop-manip.h: New file. Add prototypes. + * tree-ssa-loop-niter.c (record_niter_bound): Move to cfgloop.c. + (gcov_type_to_double_int): Move to cfgloop.h. + (double_int_cmp, bound_index, + estimate_numbers_of_iterations_loop): Make static. + (estimated_loop_iterations): Factor out get_estimated_loop_iterations. + (max_loop_iterations): Factor out get_max_loop_iterations. + (estimated_loop_iterations_int, max_stmt_executions_int): Move to + cfgloop.c. + * tree-ssa-loop-niter.h: New file. Add prototypes. + * tree-ssa-loop-prefetch.c (tree_ssa_loop_prefetch, + gate_tree_ssa_loop_prefetch, pass_data_loop_prefetch, + make_pass_loop_prefetch): Relocate from tree-ssa-loop.c. + * tree-ssa-loop-unswitch.c (tree_ssa_loop_unswitch, + gate_tree_ssa_loop_unswitch, pass_data_tree_unswitch, + make_pass_tree_unswitch): Relocate from tree-ssa-loop.c. + * tree-ssa-loop.c (tree_ssa_loop_im, gate_tree_ssa_loop_im, + pass_data_lim, make_pass_lim): Move to tree-ssa-loop-im.c. + (tree_ssa_loop_unswitch, gate_tree_ssa_loop_unswitch, + pass_data_tree_unswitch, make_pass_tree_unswitch): Move. + (tree_ssa_loop_ivcanon, gate_tree_ssa_loop_ivcanon, pass_data_iv_canon, + make_pass_iv_canon, tree_complete_unroll, gate_tree_complete_unroll, + pass_data_complete_unroll, make_pass_complete_unroll, + tree_complete_unroll_inner, gate_tree_complete_unroll_inner, + pass_data_complete_unrolli, make_pass_complete_unrolli): Move to + tree-ssa-loop-ivcanon.c. + (tree_ssa_loop_prefetch, gate_tree_ssa_loop_prefetch, + pass_data_loop_prefetch, make_pass_loop_prefetch): Move to + tree-ssa-loop-prefetch.c. + (for_each_index, lsm_tmp_name_add, gen_lsm_tmp_name): Relocate from + tree-ssa-loop-im.c. + (get_lsm_tmp_name): Relocate and add suffix parameter. + (tree_num_loop_insns): Relocate from tree-ssa-ivcanon.c. + * tree-scalar-evolution.h (simple_iv): Don't use affive_iv typedef. + * cfgloop.c (record_niter_bound, estimated_loop_iterations_int, + max_stmt_executions_int): Move from tree-ssa-loop-niter.c. + (get_estimated_loop_iterations): Factor out accessor from + estimated_loop_iterations in tree-ssa-loop-niter.c. + (get_max_loop_iterations): Factor out accessor from _max_loop_iterations + in tree-ssa-niter.c. + * loop-unroll.c (decide_unroll_constant_iterations, + decide_unroll_runtime_iterations, decide_peel_simple, + decide_unroll_stupid): Use new get_* accessors. + 2013-10-09 Marc Glisse <marc.glisse@inria.fr> PR tree-optimization/20318 diff --git a/gcc/cfgloop.c b/gcc/cfgloop.c index f39b1944ab6..272a675ab7d 100644 --- a/gcc/cfgloop.c +++ b/gcc/cfgloop.c @@ -1781,3 +1781,113 @@ get_loop_location (struct loop *loop) return DECL_SOURCE_LOCATION (current_function_decl); } +/* Records that every statement in LOOP is executed I_BOUND times. + REALISTIC is true if I_BOUND is expected to be close to the real number + of iterations. UPPER is true if we are sure the loop iterates at most + I_BOUND times. */ + +void +record_niter_bound (struct loop *loop, double_int i_bound, bool realistic, + bool upper) +{ + /* Update the bounds only when there is no previous estimation, or when the + current estimation is smaller. */ + if (upper + && (!loop->any_upper_bound + || i_bound.ult (loop->nb_iterations_upper_bound))) + { + loop->any_upper_bound = true; + loop->nb_iterations_upper_bound = i_bound; + } + if (realistic + && (!loop->any_estimate + || i_bound.ult (loop->nb_iterations_estimate))) + { + loop->any_estimate = true; + loop->nb_iterations_estimate = i_bound; + } + + /* If an upper bound is smaller than the realistic estimate of the + number of iterations, use the upper bound instead. */ + if (loop->any_upper_bound + && loop->any_estimate + && loop->nb_iterations_upper_bound.ult (loop->nb_iterations_estimate)) + loop->nb_iterations_estimate = loop->nb_iterations_upper_bound; +} + +/* Similar to estimated_loop_iterations, but returns the estimate only + if it fits to HOST_WIDE_INT. If this is not the case, or the estimate + on the number of iterations of LOOP could not be derived, returns -1. */ + +HOST_WIDE_INT +estimated_loop_iterations_int (struct loop *loop) +{ + double_int nit; + HOST_WIDE_INT hwi_nit; + + if (!get_estimated_loop_iterations (loop, &nit)) + return -1; + + if (!nit.fits_shwi ()) + return -1; + hwi_nit = nit.to_shwi (); + + return hwi_nit < 0 ? -1 : hwi_nit; +} + +/* Returns an upper bound on the number of executions of statements + in the LOOP. For statements before the loop exit, this exceeds + the number of execution of the latch by one. */ + +HOST_WIDE_INT +max_stmt_executions_int (struct loop *loop) +{ + HOST_WIDE_INT nit = max_loop_iterations_int (loop); + HOST_WIDE_INT snit; + + if (nit == -1) + return -1; + + snit = (HOST_WIDE_INT) ((unsigned HOST_WIDE_INT) nit + 1); + + /* If the computation overflows, return -1. */ + return snit < 0 ? -1 : snit; +} + +/* Sets NIT to the estimated number of executions of the latch of the + LOOP. If we have no reliable estimate, the function returns false, otherwise + returns true. */ + +bool +get_estimated_loop_iterations (struct loop *loop, double_int *nit) +{ + /* Even if the bound is not recorded, possibly we can derrive one from + profile. */ + if (!loop->any_estimate) + { + if (loop->header->count) + { + *nit = gcov_type_to_double_int + (expected_loop_iterations_unbounded (loop) + 1); + return true; + } + return false; + } + + *nit = loop->nb_iterations_estimate; + return true; +} + +/* Sets NIT to an upper bound for the maximum number of executions of the + latch of the LOOP. If we have no reliable estimate, the function returns + false, otherwise returns true. */ + +bool +get_max_loop_iterations (struct loop *loop, double_int *nit) +{ + if (!loop->any_upper_bound) + return false; + + *nit = loop->nb_iterations_upper_bound; + return true; +} diff --git a/gcc/cfgloop.h b/gcc/cfgloop.h index 33d96fe5263..9048e022607 100644 --- a/gcc/cfgloop.h +++ b/gcc/cfgloop.h @@ -255,7 +255,6 @@ extern bool flow_bb_inside_loop_p (const struct loop *, const_basic_block); extern struct loop * find_common_loop (struct loop *, struct loop *); struct loop *superloop_at_depth (struct loop *, unsigned); struct eni_weights_d; -extern unsigned tree_num_loop_insns (struct loop *, struct eni_weights_d *); extern int num_loop_insns (const struct loop *); extern int average_num_loop_insns (const struct loop *); extern unsigned get_loop_level (const struct loop *); @@ -306,16 +305,6 @@ gcov_type expected_loop_iterations_unbounded (const struct loop *); extern unsigned expected_loop_iterations (const struct loop *); extern rtx doloop_condition_get (rtx); -void estimate_numbers_of_iterations_loop (struct loop *); -void record_niter_bound (struct loop *, double_int, bool, bool); -bool estimated_loop_iterations (struct loop *, double_int *); -bool max_loop_iterations (struct loop *, double_int *); -HOST_WIDE_INT estimated_loop_iterations_int (struct loop *); -HOST_WIDE_INT max_loop_iterations_int (struct loop *); -bool max_stmt_executions (struct loop *, double_int *); -bool estimated_stmt_executions (struct loop *, double_int *); -HOST_WIDE_INT max_stmt_executions_int (struct loop *); -HOST_WIDE_INT estimated_stmt_executions_int (struct loop *); /* Loop manipulation. */ extern bool can_duplicate_loop_p (const struct loop *loop); @@ -735,7 +724,6 @@ enum extern void unroll_and_peel_loops (int); extern void doloop_optimize_loops (void); extern void move_loop_invariants (void); -extern bool finite_loop_p (struct loop *); extern void scale_loop_profile (struct loop *loop, int scale, gcov_type iteration_bound); extern vec<basic_block> get_loop_hot_path (const struct loop *loop); @@ -751,5 +739,26 @@ loop_outermost (struct loop *loop) return (*loop->superloops)[1]; } +extern void record_niter_bound (struct loop *, double_int, bool, bool); +extern HOST_WIDE_INT estimated_loop_iterations_int (struct loop *); +extern HOST_WIDE_INT max_loop_iterations_int (struct loop *); +extern bool get_estimated_loop_iterations (struct loop *loop, double_int *nit); +extern bool get_max_loop_iterations (struct loop *loop, double_int *nit); +/* Converts VAL to double_int. */ + +static inline double_int +gcov_type_to_double_int (gcov_type val) +{ + double_int ret; + + ret.low = (unsigned HOST_WIDE_INT) val; + /* If HOST_BITS_PER_WIDE_INT == HOST_BITS_PER_WIDEST_INT, avoid shifting by + the size of type. */ + val >>= HOST_BITS_PER_WIDE_INT - 1; + val >>= 1; + ret.high = (unsigned HOST_WIDE_INT) val; + + return ret; +} #endif /* GCC_CFGLOOP_H */ diff --git a/gcc/loop-unroll.c b/gcc/loop-unroll.c index 95d58209224..7fd317713fb 100644 --- a/gcc/loop-unroll.c +++ b/gcc/loop-unroll.c @@ -694,8 +694,8 @@ decide_unroll_constant_iterations (struct loop *loop, int flags) than one exit it may well loop less than determined maximal number of iterations. */ if (desc->niter < 2 * nunroll - || ((estimated_loop_iterations (loop, &iterations) - || max_loop_iterations (loop, &iterations)) + || ((get_estimated_loop_iterations (loop, &iterations) + || get_max_loop_iterations (loop, &iterations)) && iterations.ult (double_int::from_shwi (2 * nunroll)))) { if (dump_file) @@ -999,8 +999,8 @@ decide_unroll_runtime_iterations (struct loop *loop, int flags) } /* Check whether the loop rolls. */ - if ((estimated_loop_iterations (loop, &iterations) - || max_loop_iterations (loop, &iterations)) + if ((get_estimated_loop_iterations (loop, &iterations) + || get_max_loop_iterations (loop, &iterations)) && iterations.ult (double_int::from_shwi (2 * nunroll))) { if (dump_file) @@ -1388,7 +1388,7 @@ decide_peel_simple (struct loop *loop, int flags) } /* If we have realistic estimate on number of iterations, use it. */ - if (estimated_loop_iterations (loop, &iterations)) + if (get_estimated_loop_iterations (loop, &iterations)) { if (double_int::from_shwi (npeel).ule (iterations)) { @@ -1406,7 +1406,7 @@ decide_peel_simple (struct loop *loop, int flags) } /* If we have small enough bound on iterations, we can still peel (completely unroll). */ - else if (max_loop_iterations (loop, &iterations) + else if (get_max_loop_iterations (loop, &iterations) && iterations.ult (double_int::from_shwi (npeel))) npeel = iterations.to_shwi () + 1; else @@ -1556,8 +1556,8 @@ decide_unroll_stupid (struct loop *loop, int flags) } /* Check whether the loop rolls. */ - if ((estimated_loop_iterations (loop, &iterations) - || max_loop_iterations (loop, &iterations)) + if ((get_estimated_loop_iterations (loop, &iterations) + || get_max_loop_iterations (loop, &iterations)) && iterations.ult (double_int::from_shwi (2 * nunroll))) { if (dump_file) diff --git a/gcc/tree-flow-inline.h b/gcc/tree-flow-inline.h index 164df957315..8243f297747 100644 --- a/gcc/tree-flow-inline.h +++ b/gcc/tree-flow-inline.h @@ -107,21 +107,6 @@ may_be_aliased (const_tree var) || TREE_ADDRESSABLE (var))); } - -/* Returns the loop of the statement STMT. */ - -static inline struct loop * -loop_containing_stmt (gimple stmt) -{ - basic_block bb = gimple_bb (stmt); - if (!bb) - return NULL; - - return bb->loop_father; -} - - - /* Return true if VAR cannot be modified by the program. */ static inline bool diff --git a/gcc/tree-flow.h b/gcc/tree-flow.h index 54ba51aa68b..2aed9ddfee1 100644 --- a/gcc/tree-flow.h +++ b/gcc/tree-flow.h @@ -35,6 +35,7 @@ along with GCC; see the file COPYING3. If not see #include "tree-pretty-print.h" #include "gimple-low.h" #include "tree-into-ssa.h" +#include "tree-ssa-loop.h" /* This structure is used to map a gimple statement to a label, or list of labels to represent transaction restart. */ @@ -244,109 +245,19 @@ extern basic_block move_sese_region_to_fn (struct function *, basic_block, void remove_edge_and_dominated_blocks (edge); bool tree_node_can_be_shared (tree); -/* In tree-ssa-loop-ch.c */ -bool do_while_loop_p (struct loop *); - -/* Affine iv. */ - -typedef struct -{ - /* Iv = BASE + STEP * i. */ - tree base, step; - - /* True if this iv does not overflow. */ - bool no_overflow; -} affine_iv; - -/* Description of number of iterations of a loop. All the expressions inside - the structure can be evaluated at the end of the loop's preheader - (and due to ssa form, also anywhere inside the body of the loop). */ - -struct tree_niter_desc -{ - tree assumptions; /* The boolean expression. If this expression evaluates - to false, then the other fields in this structure - should not be used; there is no guarantee that they - will be correct. */ - tree may_be_zero; /* The boolean expression. If it evaluates to true, - the loop will exit in the first iteration (i.e. - its latch will not be executed), even if the niter - field says otherwise. */ - tree niter; /* The expression giving the number of iterations of - a loop (provided that assumptions == true and - may_be_zero == false), more precisely the number - of executions of the latch of the loop. */ - double_int max; /* The upper bound on the number of iterations of - the loop. */ - - /* The simplified shape of the exit condition. The loop exits if - CONTROL CMP BOUND is false, where CMP is one of NE_EXPR, - LT_EXPR, or GT_EXPR, and step of CONTROL is positive if CMP is - LE_EXPR and negative if CMP is GE_EXPR. This information is used - by loop unrolling. */ - affine_iv control; - tree bound; - enum tree_code cmp; -}; /* In tree-ssa-loop*.c */ -unsigned int tree_ssa_lim (void); -unsigned int tree_ssa_unswitch_loops (void); -unsigned int canonicalize_induction_variables (void); -unsigned int tree_unroll_loops_completely (bool, bool); -unsigned int tree_ssa_prefetch_arrays (void); -void tree_ssa_iv_optimize (void); unsigned tree_predictive_commoning (void); -tree canonicalize_loop_ivs (struct loop *, tree *, bool); bool parallelize_loops (void); -bool loop_only_exit_p (const struct loop *, const_edge); -bool number_of_iterations_exit (struct loop *, edge, - struct tree_niter_desc *niter, bool, - bool every_iteration = true); -tree find_loop_niter (struct loop *, edge *); -tree loop_niter_by_eval (struct loop *, edge); -tree find_loop_niter_by_eval (struct loop *, edge *); -void estimate_numbers_of_iterations (void); -bool scev_probably_wraps_p (tree, tree, gimple, struct loop *, bool); bool convert_affine_scev (struct loop *, tree, tree *, tree *, gimple, bool); -bool nowrap_type_p (tree); enum ev_direction {EV_DIR_GROWS, EV_DIR_DECREASES, EV_DIR_UNKNOWN}; enum ev_direction scev_direction (const_tree); -void free_numbers_of_iterations_estimates (void); -void free_numbers_of_iterations_estimates_loop (struct loop *); -void rewrite_into_loop_closed_ssa (bitmap, unsigned); -void verify_loop_closed_ssa (bool); -bool for_each_index (tree *, bool (*) (tree, tree *, void *), void *); -void create_iv (tree, tree, tree, struct loop *, gimple_stmt_iterator *, bool, - tree *, tree *); -basic_block split_loop_exit_edge (edge); -void standard_iv_increment_position (struct loop *, gimple_stmt_iterator *, - bool *); -basic_block ip_end_pos (struct loop *); -basic_block ip_normal_pos (struct loop *); -bool gimple_duplicate_loop_to_header_edge (struct loop *, edge, - unsigned int, sbitmap, - edge, vec<edge> *, - int); struct loop *slpeel_tree_duplicate_loop_to_edge_cfg (struct loop *, edge); -tree expand_simple_operations (tree); -void substitute_in_loop_info (struct loop *, tree, tree); -edge single_dom_exit (struct loop *); -bool can_unroll_loop_p (struct loop *loop, unsigned factor, - struct tree_niter_desc *niter); -void tree_unroll_loop (struct loop *, unsigned, - edge, struct tree_niter_desc *); -typedef void (*transform_callback)(struct loop *, void *); -void tree_transform_and_unroll_loop (struct loop *, unsigned, - edge, struct tree_niter_desc *, - transform_callback, void *); -bool contains_abnormal_ssa_name_p (tree); -bool stmt_dominates_stmt_p (gimple, gimple); /* In tree-ssa-threadedge.c */ extern void threadedge_initialize_values (void); @@ -362,19 +273,6 @@ extern void thread_across_edge (gimple, edge, bool, vec<tree> *, tree (*) (gimple, gimple)); extern void propagate_threaded_block_debug_into (basic_block, basic_block); -/* In tree-ssa-loop-im.c */ -/* The possibilities of statement movement. */ - -enum move_pos - { - MOVE_IMPOSSIBLE, /* No movement -- side effect expression. */ - MOVE_PRESERVE_EXECUTION, /* Must not cause the non-executed statement - become executed -- memory accesses, ... */ - MOVE_POSSIBLE /* Unlimited movement. */ - }; -extern enum move_pos movement_possibility (gimple); -char *get_lsm_tmp_name (tree, unsigned); - /* In tree-loop-linear.c */ extern void linear_transform_loops (void); extern unsigned perfect_loop_nest_depth (struct loop *); @@ -385,14 +283,6 @@ extern void graphite_transform_loops (void); /* In tree-data-ref.c */ extern void tree_check_data_deps (void); -/* In tree-ssa-loop-ivopts.c */ -bool expr_invariant_in_loop_p (struct loop *, tree); -bool stmt_invariant_in_loop_p (struct loop *, gimple); -struct loop *outermost_invariant_loop_for_expr (struct loop *, tree); -bool multiplier_allowed_in_address_p (HOST_WIDE_INT, enum machine_mode, - addr_space_t); -bool may_be_nonaddressable_p (tree expr); - /* In gimplify.c */ tree force_gimple_operand_1 (tree, gimple_seq *, gimple_predicate, tree); tree force_gimple_operand (tree, gimple_seq *, bool, tree); diff --git a/gcc/tree-scalar-evolution.h b/gcc/tree-scalar-evolution.h index 55ba82c5dbd..db7ac4c66f0 100644 --- a/gcc/tree-scalar-evolution.h +++ b/gcc/tree-scalar-evolution.h @@ -36,7 +36,8 @@ extern tree resolve_mixers (struct loop *, tree); extern void gather_stats_on_scev_database (void); extern unsigned int scev_const_prop (void); extern bool expression_expensive_p (tree); -extern bool simple_iv (struct loop *, struct loop *, tree, affine_iv *, bool); +extern bool simple_iv (struct loop *, struct loop *, tree, struct affine_iv_d *, + bool); extern tree compute_overall_effect_of_inner_loop (struct loop *, tree); /* Returns the basic block preceding LOOP or ENTRY_BLOCK_PTR when the diff --git a/gcc/tree-ssa-loop-ch.c b/gcc/tree-ssa-loop-ch.c index faa6bbcc585..b74855e62de 100644 --- a/gcc/tree-ssa-loop-ch.c +++ b/gcc/tree-ssa-loop-ch.c @@ -29,7 +29,6 @@ along with GCC; see the file COPYING3. If not see #include "cfgloop.h" #include "tree-inline.h" #include "flags.h" -#include "tree-inline.h" /* Duplicates headers of loops if they are small enough, so that the statements in the loop body are always executed when the loop is entered. This @@ -100,7 +99,7 @@ should_duplicate_loop_header_p (basic_block header, struct loop *loop, /* Checks whether LOOP is a do-while style loop. */ -bool +static bool do_while_loop_p (struct loop *loop) { gimple stmt = last_stmt (loop->latch); diff --git a/gcc/tree-ssa-loop-im.c b/gcc/tree-ssa-loop-im.c index fc255289f24..84f50cdb92d 100644 --- a/gcc/tree-ssa-loop-im.c +++ b/gcc/tree-ssa-loop-im.c @@ -242,98 +242,16 @@ clear_lim_data (gimple stmt) *p = NULL; } -/* Calls CBCK for each index in memory reference ADDR_P. There are two - kinds situations handled; in each of these cases, the memory reference - and DATA are passed to the callback: - Access to an array: ARRAY_{RANGE_}REF (base, index). In this case we also - pass the pointer to the index to the callback. - - Pointer dereference: INDIRECT_REF (addr). In this case we also pass the - pointer to addr to the callback. - - If the callback returns false, the whole search stops and false is returned. - Otherwise the function returns true after traversing through the whole - reference *ADDR_P. */ - -bool -for_each_index (tree *addr_p, bool (*cbck) (tree, tree *, void *), void *data) -{ - tree *nxt, *idx; - - for (; ; addr_p = nxt) - { - switch (TREE_CODE (*addr_p)) - { - case SSA_NAME: - return cbck (*addr_p, addr_p, data); - - case MEM_REF: - nxt = &TREE_OPERAND (*addr_p, 0); - return cbck (*addr_p, nxt, data); - - case BIT_FIELD_REF: - case VIEW_CONVERT_EXPR: - case REALPART_EXPR: - case IMAGPART_EXPR: - nxt = &TREE_OPERAND (*addr_p, 0); - break; - - case COMPONENT_REF: - /* If the component has varying offset, it behaves like index - as well. */ - idx = &TREE_OPERAND (*addr_p, 2); - if (*idx - && !cbck (*addr_p, idx, data)) - return false; - - nxt = &TREE_OPERAND (*addr_p, 0); - break; +/* The possibilities of statement movement. */ +enum move_pos + { + MOVE_IMPOSSIBLE, /* No movement -- side effect expression. */ + MOVE_PRESERVE_EXECUTION, /* Must not cause the non-executed statement + become executed -- memory accesses, ... */ + MOVE_POSSIBLE /* Unlimited movement. */ + }; - case ARRAY_REF: - case ARRAY_RANGE_REF: - nxt = &TREE_OPERAND (*addr_p, 0); - if (!cbck (*addr_p, &TREE_OPERAND (*addr_p, 1), data)) - return false; - break; - - case VAR_DECL: - case PARM_DECL: - case CONST_DECL: - case STRING_CST: - case RESULT_DECL: - case VECTOR_CST: - case COMPLEX_CST: - case INTEGER_CST: - case REAL_CST: - case FIXED_CST: - case CONSTRUCTOR: - return true; - - case ADDR_EXPR: - gcc_assert (is_gimple_min_invariant (*addr_p)); - return true; - - case TARGET_MEM_REF: - idx = &TMR_BASE (*addr_p); - if (*idx - && !cbck (*addr_p, idx, data)) - return false; - idx = &TMR_INDEX (*addr_p); - if (*idx - && !cbck (*addr_p, idx, data)) - return false; - idx = &TMR_INDEX2 (*addr_p); - if (*idx - && !cbck (*addr_p, idx, data)) - return false; - return true; - - default: - gcc_unreachable (); - } - } -} /* If it is possible to hoist the statement STMT unconditionally, returns MOVE_POSSIBLE. @@ -1741,122 +1659,6 @@ first_mem_ref_loc (struct loop *loop, mem_ref_p ref) return locp; } -/* The name and the length of the currently generated variable - for lsm. */ -#define MAX_LSM_NAME_LENGTH 40 -static char lsm_tmp_name[MAX_LSM_NAME_LENGTH + 1]; -static int lsm_tmp_name_length; - -/* Adds S to lsm_tmp_name. */ - -static void -lsm_tmp_name_add (const char *s) -{ - int l = strlen (s) + lsm_tmp_name_length; - if (l > MAX_LSM_NAME_LENGTH) - return; - - strcpy (lsm_tmp_name + lsm_tmp_name_length, s); - lsm_tmp_name_length = l; -} - -/* Stores the name for temporary variable that replaces REF to - lsm_tmp_name. */ - -static void -gen_lsm_tmp_name (tree ref) -{ - const char *name; - - switch (TREE_CODE (ref)) - { - case MEM_REF: - case TARGET_MEM_REF: - gen_lsm_tmp_name (TREE_OPERAND (ref, 0)); - lsm_tmp_name_add ("_"); - break; - - case ADDR_EXPR: - gen_lsm_tmp_name (TREE_OPERAND (ref, 0)); - break; - - case BIT_FIELD_REF: - case VIEW_CONVERT_EXPR: - case ARRAY_RANGE_REF: - gen_lsm_tmp_name (TREE_OPERAND (ref, 0)); - break; - - case REALPART_EXPR: - gen_lsm_tmp_name (TREE_OPERAND (ref, 0)); - lsm_tmp_name_add ("_RE"); - break; - - case IMAGPART_EXPR: - gen_lsm_tmp_name (TREE_OPERAND (ref, 0)); - lsm_tmp_name_add ("_IM"); - break; - - case COMPONENT_REF: - gen_lsm_tmp_name (TREE_OPERAND (ref, 0)); - lsm_tmp_name_add ("_"); - name = get_name (TREE_OPERAND (ref, 1)); - if (!name) - name = "F"; - lsm_tmp_name_add (name); - break; - - case ARRAY_REF: - gen_lsm_tmp_name (TREE_OPERAND (ref, 0)); - lsm_tmp_name_add ("_I"); - break; - - case SSA_NAME: - case VAR_DECL: - case PARM_DECL: - name = get_name (ref); - if (!name) - name = "D"; - lsm_tmp_name_add (name); - break; - - case STRING_CST: - lsm_tmp_name_add ("S"); - break; - - case RESULT_DECL: - lsm_tmp_name_add ("R"); - break; - - case INTEGER_CST: - /* Nothing. */ - break; - - default: - gcc_unreachable (); - } -} - -/* Determines name for temporary variable that replaces REF. - The name is accumulated into the lsm_tmp_name variable. - N is added to the name of the temporary. */ - -char * -get_lsm_tmp_name (tree ref, unsigned n) -{ - char ns[2]; - - lsm_tmp_name_length = 0; - gen_lsm_tmp_name (ref); - lsm_tmp_name_add ("_lsm"); - if (n < 10) - { - ns[0] = '0' + n; - ns[1] = 0; - lsm_tmp_name_add (ns); - } - return lsm_tmp_name; -} - struct prev_flag_edges { /* Edge to insert new flag comparison code. */ edge append_cond_position; @@ -2026,8 +1828,7 @@ static tree execute_sm_if_changed_flag_set (struct loop *loop, mem_ref_p ref) { tree flag; - char *str = get_lsm_tmp_name (ref->mem.ref, ~0); - lsm_tmp_name_add ("_flag"); + char *str = get_lsm_tmp_name (ref->mem.ref, ~0, "_flag"); flag = create_tmp_reg (boolean_type_node, str); for_all_locs_in_loop (loop, ref, sm_set_flag_if_changed (flag)); return flag; @@ -2639,3 +2440,61 @@ tree_ssa_lim (void) return todo; } + +/* Loop invariant motion pass. */ + +static unsigned int +tree_ssa_loop_im (void) +{ + if (number_of_loops (cfun) <= 1) + return 0; + + return tree_ssa_lim (); +} + +static bool +gate_tree_ssa_loop_im (void) +{ + return flag_tree_loop_im != 0; +} + +namespace { + +const pass_data pass_data_lim = +{ + GIMPLE_PASS, /* type */ + "lim", /* name */ + OPTGROUP_LOOP, /* optinfo_flags */ + true, /* has_gate */ + true, /* has_execute */ + TV_LIM, /* tv_id */ + PROP_cfg, /* properties_required */ + 0, /* properties_provided */ + 0, /* properties_destroyed */ + 0, /* todo_flags_start */ + 0, /* todo_flags_finish */ +}; + +class pass_lim : public gimple_opt_pass +{ +public: + pass_lim (gcc::context *ctxt) + : gimple_opt_pass (pass_data_lim, ctxt) + {} + + /* opt_pass methods: */ + opt_pass * clone () { return new pass_lim (m_ctxt); } + bool gate () { return gate_tree_ssa_loop_im (); } + unsigned int execute () { return tree_ssa_loop_im (); } + +}; // class pass_lim + +} // anon namespace + +gimple_opt_pass * +make_pass_lim (gcc::context *ctxt) +{ + return new pass_lim (ctxt); +} + + diff --git a/gcc/tree-ssa-loop-ivcanon.c b/gcc/tree-ssa-loop-ivcanon.c index d5249baeab0..8db5b9ede7e 100644 --- a/gcc/tree-ssa-loop-ivcanon.c +++ b/gcc/tree-ssa-loop-ivcanon.c @@ -107,23 +107,6 @@ create_canonical_iv (struct loop *loop, edge exit, tree niter) update_stmt (cond); } -/* Computes an estimated number of insns in LOOP, weighted by WEIGHTS. */ - -unsigned -tree_num_loop_insns (struct loop *loop, eni_weights *weights) -{ - basic_block *body = get_loop_body (loop); - gimple_stmt_iterator gsi; - unsigned size = 0, i; - - for (i = 0; i < loop->num_nodes; i++) - for (gsi = gsi_start_bb (body[i]); !gsi_end_p (gsi); gsi_next (&gsi)) - size += estimate_num_insns (gsi_stmt (gsi), weights); - free (body); - - return size; -} - /* Describe size of loop as detected by tree_estimate_loop_size. */ struct loop_size { @@ -422,7 +405,7 @@ estimated_unrolled_size (struct loop_size *size, loop-niter identified as having undefined effect in the last iteration. The other cases are hopefully rare and will be cleaned up later. */ -edge +static edge loop_edge_to_cancel (struct loop *loop) { vec<edge> exits; @@ -598,7 +581,7 @@ static vec<int> loops_to_unloop_nunroll; LOOP_CLOSED_SSA_INVALIDATED is used to bookkepp the case when we need to go into loop closed SSA form. */ -void +static void unloop_loops (bitmap loop_closed_ssa_invalidated, bool *irred_invalidated) { @@ -1253,3 +1236,182 @@ tree_unroll_loops_completely (bool may_increase_size, bool unroll_outer) return 0; } + +/* Canonical induction variable creation pass. */ + +static unsigned int +tree_ssa_loop_ivcanon (void) +{ + if (number_of_loops (cfun) <= 1) + return 0; + + return canonicalize_induction_variables (); +} + +static bool +gate_tree_ssa_loop_ivcanon (void) +{ + return flag_tree_loop_ivcanon != 0; +} + +namespace { + +const pass_data pass_data_iv_canon = +{ + GIMPLE_PASS, /* type */ + "ivcanon", /* name */ + OPTGROUP_LOOP, /* optinfo_flags */ + true, /* has_gate */ + true, /* has_execute */ + TV_TREE_LOOP_IVCANON, /* tv_id */ + ( PROP_cfg | PROP_ssa ), /* properties_required */ + 0, /* properties_provided */ + 0, /* properties_destroyed */ + 0, /* todo_flags_start */ + 0, /* todo_flags_finish */ +}; + +class pass_iv_canon : public gimple_opt_pass +{ +public: + pass_iv_canon (gcc::context *ctxt) + : gimple_opt_pass (pass_data_iv_canon, ctxt) + {} + + /* opt_pass methods: */ + bool gate () { return gate_tree_ssa_loop_ivcanon (); } + unsigned int execute () { return tree_ssa_loop_ivcanon (); } + +}; // class pass_iv_canon + +} // anon namespace + +gimple_opt_pass * +make_pass_iv_canon (gcc::context *ctxt) +{ + return new pass_iv_canon (ctxt); +} + +/* Complete unrolling of loops. */ + +static unsigned int +tree_complete_unroll (void) +{ + if (number_of_loops (cfun) <= 1) + return 0; + + return tree_unroll_loops_completely (flag_unroll_loops + || flag_peel_loops + || optimize >= 3, true); +} + +static bool +gate_tree_complete_unroll (void) +{ + return true; +} + +namespace { + +const pass_data pass_data_complete_unroll = +{ + GIMPLE_PASS, /* type */ + "cunroll", /* name */ + OPTGROUP_LOOP, /* optinfo_flags */ + true, /* has_gate */ + true, /* has_execute */ + TV_COMPLETE_UNROLL, /* tv_id */ + ( PROP_cfg | PROP_ssa ), /* properties_required */ + 0, /* properties_provided */ + 0, /* properties_destroyed */ + 0, /* todo_flags_start */ + 0, /* todo_flags_finish */ +}; + +class pass_complete_unroll : public gimple_opt_pass +{ +public: + pass_complete_unroll (gcc::context *ctxt) + : gimple_opt_pass (pass_data_complete_unroll, ctxt) + {} + + /* opt_pass methods: */ + bool gate () { return gate_tree_complete_unroll (); } + unsigned int execute () { return tree_complete_unroll (); } + +}; // class pass_complete_unroll + +} // anon namespace + +gimple_opt_pass * +make_pass_complete_unroll (gcc::context *ctxt) +{ + return new pass_complete_unroll (ctxt); +} + +/* Complete unrolling of inner loops. */ + +static unsigned int +tree_complete_unroll_inner (void) +{ + unsigned ret = 0; + + loop_optimizer_init (LOOPS_NORMAL + | LOOPS_HAVE_RECORDED_EXITS); + if (number_of_loops (cfun) > 1) + { + scev_initialize (); + ret = tree_unroll_loops_completely (optimize >= 3, false); + free_numbers_of_iterations_estimates (); + scev_finalize (); + } + loop_optimizer_finalize (); + + return ret; +} + +static bool +gate_tree_complete_unroll_inner (void) +{ + return optimize >= 2; +} + +namespace { + +const pass_data pass_data_complete_unrolli = +{ + GIMPLE_PASS, /* type */ + "cunrolli", /* name */ + OPTGROUP_LOOP, /* optinfo_flags */ + true, /* has_gate */ + true, /* has_execute */ + TV_COMPLETE_UNROLL, /* tv_id */ + ( PROP_cfg | PROP_ssa ), /* properties_required */ + 0, /* properties_provided */ + 0, /* properties_destroyed */ + 0, /* todo_flags_start */ + TODO_verify_flow, /* todo_flags_finish */ +}; + +class pass_complete_unrolli : public gimple_opt_pass +{ +public: + pass_complete_unrolli (gcc::context *ctxt) + : gimple_opt_pass (pass_data_complete_unrolli, ctxt) + {} + + /* opt_pass methods: */ + bool gate () { return gate_tree_complete_unroll_inner (); } + unsigned int execute () { return tree_complete_unroll_inner (); } + +}; // class pass_complete_unrolli + +} // anon namespace + +gimple_opt_pass * +make_pass_complete_unrolli (gcc::context *ctxt) +{ + return new pass_complete_unrolli (ctxt); +} + + diff --git a/gcc/tree-ssa-loop-ivopts.c b/gcc/tree-ssa-loop-ivopts.c index 7b684a62819..5e8fa36f394 100644 --- a/gcc/tree-ssa-loop-ivopts.c +++ b/gcc/tree-ssa-loop-ivopts.c @@ -452,7 +452,6 @@ single_dom_exit (struct loop *loop) /* Dumps information about the induction variable IV to FILE. */ -extern void dump_iv (FILE *, struct iv *); void dump_iv (FILE *file, struct iv *iv) { @@ -497,7 +496,6 @@ dump_iv (FILE *file, struct iv *iv) /* Dumps information about the USE to FILE. */ -extern void dump_use (FILE *, struct iv_use *); void dump_use (FILE *file, struct iv_use *use) { @@ -541,7 +539,6 @@ dump_use (FILE *file, struct iv_use *use) /* Dumps information about the uses to FILE. */ -extern void dump_uses (FILE *, struct ivopts_data *); void dump_uses (FILE *file, struct ivopts_data *data) { @@ -559,7 +556,6 @@ dump_uses (FILE *file, struct ivopts_data *data) /* Dumps information about induction variable candidate CAND to FILE. */ -extern void dump_cand (FILE *, struct iv_cand *); void dump_cand (FILE *file, struct iv_cand *cand) { @@ -1454,29 +1450,6 @@ expr_invariant_in_loop_p (struct loop *loop, tree expr) return true; } -/* Returns true if statement STMT is obviously invariant in LOOP, - i.e. if all its operands on the RHS are defined outside of the LOOP. - LOOP should not be the function body. */ - -bool -stmt_invariant_in_loop_p (struct loop *loop, gimple stmt) -{ - unsigned i; - tree lhs; - - gcc_assert (loop_depth (loop) > 0); - - lhs = gimple_get_lhs (stmt); - for (i = 0; i < gimple_num_ops (stmt); i++) - { - tree op = gimple_op (stmt, i); - if (op != lhs && !expr_invariant_in_loop_p (loop, op)) - return false; - } - - return true; -} - /* Cumulates the steps of indices into DATA and replaces their values with the initial ones. Returns false when the value of the index cannot be determined. Callback for for_each_index. */ diff --git a/gcc/tree-ssa-loop-ivopts.h b/gcc/tree-ssa-loop-ivopts.h new file mode 100644 index 00000000000..1af92be21a8 --- /dev/null +++ b/gcc/tree-ssa-loop-ivopts.h @@ -0,0 +1,36 @@ +/* Header file for Induction variable optimizations. + Copyright (C) 2013 Free Software Foundation, Inc. + +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/>. */ + +#ifndef GCC_TREE_SSA_LOOP_IVOPTS_H +#define GCC_TREE_SSA_LOOP_IVOPTS_H + +extern edge single_dom_exit (struct loop *); +extern void dump_iv (FILE *, struct iv *); +extern void dump_use (FILE *, struct iv_use *); +extern void dump_uses (FILE *, struct ivopts_data *); +extern void dump_cand (FILE *, struct iv_cand *); +extern bool contains_abnormal_ssa_name_p (tree); +extern struct loop *outermost_invariant_loop_for_expr (struct loop *, tree); +extern bool expr_invariant_in_loop_p (struct loop *, tree); +bool may_be_nonaddressable_p (tree expr); +bool multiplier_allowed_in_address_p (HOST_WIDE_INT, enum machine_mode, + addr_space_t); +void tree_ssa_iv_optimize (void); + +#endif /* GCC_TREE_SSA_LOOP_IVOPTS_H */ diff --git a/gcc/tree-ssa-loop-manip.h b/gcc/tree-ssa-loop-manip.h new file mode 100644 index 00000000000..a1dcd22193d --- /dev/null +++ b/gcc/tree-ssa-loop-manip.h @@ -0,0 +1,49 @@ +/* Header file for High-level loop manipulation functions. + Copyright (C) 2013 Free Software Foundation, Inc. + +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/>. */ + +#ifndef GCC_TREE_SSA_LOOP_MANIP_H +#define GCC_TREE_SSA_LOOP_MANIP_H + +typedef void (*transform_callback)(struct loop *, void *); + +extern void create_iv (tree, tree, tree, struct loop *, gimple_stmt_iterator *, + bool, tree *, tree *); +extern void rewrite_into_loop_closed_ssa (bitmap, unsigned); +extern void verify_loop_closed_ssa (bool); +extern basic_block split_loop_exit_edge (edge); +extern basic_block ip_end_pos (struct loop *); +extern basic_block ip_normal_pos (struct loop *); +extern void standard_iv_increment_position (struct loop *, + gimple_stmt_iterator *, bool *); +extern bool gimple_duplicate_loop_to_header_edge (struct loop *, edge, + unsigned int, sbitmap, + edge, vec<edge> *, + int); +extern bool can_unroll_loop_p (struct loop *loop, unsigned factor, + struct tree_niter_desc *niter); +extern void tree_transform_and_unroll_loop (struct loop *, unsigned, + edge, struct tree_niter_desc *, + transform_callback, void *); +extern void tree_unroll_loop (struct loop *, unsigned, + edge, struct tree_niter_desc *); +extern tree canonicalize_loop_ivs (struct loop *, tree *, bool); + + + +#endif /* GCC_TREE_SSA_LOOP_MANIP_H */ diff --git a/gcc/tree-ssa-loop-niter.c b/gcc/tree-ssa-loop-niter.c index adbfe8e8c21..8bcb1c6b26e 100644 --- a/gcc/tree-ssa-loop-niter.c +++ b/gcc/tree-ssa-loop-niter.c @@ -39,6 +39,7 @@ along with GCC; see the file COPYING3. If not see #include "tree-inline.h" #include "tree-pass.h" + #define SWAP(X, Y) do { affine_iv *tmp = (X); (X) = (Y); (Y) = tmp; } while (0) /* The maximum number of dominator BBs we search for conditions @@ -2507,40 +2508,6 @@ derive_constant_upper_bound_ops (tree type, tree op0, } } -/* Records that every statement in LOOP is executed I_BOUND times. - REALISTIC is true if I_BOUND is expected to be close to the real number - of iterations. UPPER is true if we are sure the loop iterates at most - I_BOUND times. */ - -void -record_niter_bound (struct loop *loop, double_int i_bound, bool realistic, - bool upper) -{ - /* Update the bounds only when there is no previous estimation, or when the - current estimation is smaller. */ - if (upper - && (!loop->any_upper_bound - || i_bound.ult (loop->nb_iterations_upper_bound))) - { - loop->any_upper_bound = true; - loop->nb_iterations_upper_bound = i_bound; - } - if (realistic - && (!loop->any_estimate - || i_bound.ult (loop->nb_iterations_estimate))) - { - loop->any_estimate = true; - loop->nb_iterations_estimate = i_bound; - } - - /* If an upper bound is smaller than the realistic estimate of the - number of iterations, use the upper bound instead. */ - if (loop->any_upper_bound - && loop->any_estimate - && loop->nb_iterations_upper_bound.ult (loop->nb_iterations_estimate)) - loop->nb_iterations_estimate = loop->nb_iterations_upper_bound; -} - /* Emit a -Waggressive-loop-optimizations warning if needed. */ static void @@ -3008,26 +2975,11 @@ infer_loop_bounds_from_undefined (struct loop *loop) free (bbs); } -/* Converts VAL to double_int. */ -static double_int -gcov_type_to_double_int (gcov_type val) -{ - double_int ret; - - ret.low = (unsigned HOST_WIDE_INT) val; - /* If HOST_BITS_PER_WIDE_INT == HOST_BITS_PER_WIDEST_INT, avoid shifting by - the size of type. */ - val >>= HOST_BITS_PER_WIDE_INT - 1; - val >>= 1; - ret.high = (unsigned HOST_WIDE_INT) val; - - return ret; -} /* Compare double ints, callback for qsort. */ -int +static int double_int_cmp (const void *p1, const void *p2) { const double_int *d1 = (const double_int *)p1; @@ -3042,7 +2994,7 @@ double_int_cmp (const void *p1, const void *p2) /* Return index of BOUND in BOUNDS array sorted in increasing order. Lookup by binary search. */ -int +static int bound_index (vec<double_int> bounds, double_int bound) { unsigned int end = bounds.length (); @@ -3349,7 +3301,7 @@ maybe_lower_iteration_bound (struct loop *loop) /* Records estimates on numbers of iterations of LOOP. If USE_UNDEFINED_P is true also use estimates derived from undefined behavior. */ -void +static void estimate_numbers_of_iterations_loop (struct loop *loop) { vec<edge> exits; @@ -3433,21 +3385,7 @@ estimated_loop_iterations (struct loop *loop, double_int *nit) if (scev_initialized_p ()) estimate_numbers_of_iterations_loop (loop); - /* Even if the bound is not recorded, possibly we can derrive one from - profile. */ - if (!loop->any_estimate) - { - if (loop->header->count) - { - *nit = gcov_type_to_double_int - (expected_loop_iterations_unbounded (loop) + 1); - return true; - } - return false; - } - - *nit = loop->nb_iterations_estimate; - return true; + return (get_estimated_loop_iterations (loop, nit)); } /* Sets NIT to an upper bound for the maximum number of executions of the @@ -3461,31 +3399,8 @@ max_loop_iterations (struct loop *loop, double_int *nit) estimate. Otherwise just return whatever we recorded earlier. */ if (scev_initialized_p ()) estimate_numbers_of_iterations_loop (loop); - if (!loop->any_upper_bound) - return false; - - *nit = loop->nb_iterations_upper_bound; - return true; -} - -/* Similar to estimated_loop_iterations, but returns the estimate only - if it fits to HOST_WIDE_INT. If this is not the case, or the estimate - on the number of iterations of LOOP could not be derived, returns -1. */ -HOST_WIDE_INT -estimated_loop_iterations_int (struct loop *loop) -{ - double_int nit; - HOST_WIDE_INT hwi_nit; - - if (!estimated_loop_iterations (loop, &nit)) - return -1; - - if (!nit.fits_shwi ()) - return -1; - hwi_nit = nit.to_shwi (); - - return hwi_nit < 0 ? -1 : hwi_nit; + return get_max_loop_iterations (loop, nit); } /* Similar to max_loop_iterations, but returns the estimate only @@ -3508,25 +3423,6 @@ max_loop_iterations_int (struct loop *loop) return hwi_nit < 0 ? -1 : hwi_nit; } -/* Returns an upper bound on the number of executions of statements - in the LOOP. For statements before the loop exit, this exceeds - the number of execution of the latch by one. */ - -HOST_WIDE_INT -max_stmt_executions_int (struct loop *loop) -{ - HOST_WIDE_INT nit = max_loop_iterations_int (loop); - HOST_WIDE_INT snit; - - if (nit == -1) - return -1; - - snit = (HOST_WIDE_INT) ((unsigned HOST_WIDE_INT) nit + 1); - - /* If the computation overflows, return -1. */ - return snit < 0 ? -1 : snit; -} - /* Returns an estimate for the number of executions of statements in the LOOP. For statements before the loop exit, this exceeds the number of execution of the latch by one. */ diff --git a/gcc/tree-ssa-loop-niter.h b/gcc/tree-ssa-loop-niter.h new file mode 100644 index 00000000000..aa05282c59d --- /dev/null +++ b/gcc/tree-ssa-loop-niter.h @@ -0,0 +1,46 @@ +/* Header file for loop interation estimates. + Copyright (C) 2013 Free Software Foundation, Inc. + +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/>. */ + +#ifndef GCC_TREE_SSA_LOOP_NITER_H +#define GCC_TREE_SSA_LOOP_NITER_H + +extern tree expand_simple_operations (tree); +extern bool loop_only_exit_p (const struct loop *, const_edge); +extern bool number_of_iterations_exit (struct loop *, edge, + struct tree_niter_desc *niter, bool, + bool every_iteration = true); +extern tree find_loop_niter (struct loop *, edge *); +extern bool finite_loop_p (struct loop *); +extern tree loop_niter_by_eval (struct loop *, edge); +extern tree find_loop_niter_by_eval (struct loop *, edge *); +extern bool estimated_loop_iterations (struct loop *, double_int *); +extern bool max_loop_iterations (struct loop *, double_int *); +extern HOST_WIDE_INT max_stmt_executions_int (struct loop *); +extern HOST_WIDE_INT estimated_stmt_executions_int (struct loop *); +extern bool max_stmt_executions (struct loop *, double_int *); +extern bool estimated_stmt_executions (struct loop *, double_int *); +extern void estimate_numbers_of_iterations (void); +extern bool stmt_dominates_stmt_p (gimple, gimple); +extern bool nowrap_type_p (tree); +extern bool scev_probably_wraps_p (tree, tree, gimple, struct loop *, bool); +extern void free_numbers_of_iterations_estimates_loop (struct loop *); +extern void free_numbers_of_iterations_estimates (void); +extern void substitute_in_loop_info (struct loop *, tree, tree); + +#endif /* GCC_TREE_SSA_LOOP_NITER_H */ diff --git a/gcc/tree-ssa-loop-prefetch.c b/gcc/tree-ssa-loop-prefetch.c index d75155d15d6..5a51ba66c49 100644 --- a/gcc/tree-ssa-loop-prefetch.c +++ b/gcc/tree-ssa-loop-prefetch.c @@ -1988,3 +1988,60 @@ tree_ssa_prefetch_arrays (void) free_original_copy_tables (); return todo_flags; } + +/* Prefetching. */ + +static unsigned int +tree_ssa_loop_prefetch (void) +{ + if (number_of_loops (cfun) <= 1) + return 0; + + return tree_ssa_prefetch_arrays (); +} + +static bool +gate_tree_ssa_loop_prefetch (void) +{ + return flag_prefetch_loop_arrays > 0; +} + +namespace { + +const pass_data pass_data_loop_prefetch = +{ + GIMPLE_PASS, /* type */ + "aprefetch", /* name */ + OPTGROUP_LOOP, /* optinfo_flags */ + true, /* has_gate */ + true, /* has_execute */ + TV_TREE_PREFETCH, /* tv_id */ + ( PROP_cfg | PROP_ssa ), /* properties_required */ + 0, /* properties_provided */ + 0, /* properties_destroyed */ + 0, /* todo_flags_start */ + 0, /* todo_flags_finish */ +}; + +class pass_loop_prefetch : public gimple_opt_pass +{ +public: + pass_loop_prefetch (gcc::context *ctxt) + : gimple_opt_pass (pass_data_loop_prefetch, ctxt) + {} + + /* opt_pass methods: */ + bool gate () { return gate_tree_ssa_loop_prefetch (); } + unsigned int execute () { return tree_ssa_loop_prefetch (); } + +}; // class pass_loop_prefetch + +} // anon namespace + +gimple_opt_pass * +make_pass_loop_prefetch (gcc::context *ctxt) +{ + return new pass_loop_prefetch (ctxt); +} + + diff --git a/gcc/tree-ssa-loop-unswitch.c b/gcc/tree-ssa-loop-unswitch.c index 6ce06c1326c..74af9758b1a 100644 --- a/gcc/tree-ssa-loop-unswitch.c +++ b/gcc/tree-ssa-loop-unswitch.c @@ -388,3 +388,60 @@ tree_unswitch_loop (struct loop *loop, NULL, prob_true, prob_true, REG_BR_PROB_BASE - prob_true, false); } + +/* Loop unswitching pass. */ + +static unsigned int +tree_ssa_loop_unswitch (void) +{ + if (number_of_loops (cfun) <= 1) + return 0; + + return tree_ssa_unswitch_loops (); +} + +static bool +gate_tree_ssa_loop_unswitch (void) +{ + return flag_unswitch_loops != 0; +} + +namespace { + +const pass_data pass_data_tree_unswitch = +{ + GIMPLE_PASS, /* type */ + "unswitch", /* name */ + OPTGROUP_LOOP, /* optinfo_flags */ + true, /* has_gate */ + true, /* has_execute */ + TV_TREE_LOOP_UNSWITCH, /* tv_id */ + PROP_cfg, /* properties_required */ + 0, /* properties_provided */ + 0, /* properties_destroyed */ + 0, /* todo_flags_start */ + 0, /* todo_flags_finish */ +}; + +class pass_tree_unswitch : public gimple_opt_pass +{ +public: + pass_tree_unswitch (gcc::context *ctxt) + : gimple_opt_pass (pass_data_tree_unswitch, ctxt) + {} + + /* opt_pass methods: */ + bool gate () { return gate_tree_ssa_loop_unswitch (); } + unsigned int execute () { return tree_ssa_loop_unswitch (); } + +}; // class pass_tree_unswitch + +} // anon namespace + +gimple_opt_pass * +make_pass_tree_unswitch (gcc::context *ctxt) +{ + return new pass_tree_unswitch (ctxt); +} + + diff --git a/gcc/tree-ssa-loop.c b/gcc/tree-ssa-loop.c index 3952029d0ea..bf2fbc885d6 100644 --- a/gcc/tree-ssa-loop.c +++ b/gcc/tree-ssa-loop.c @@ -134,117 +134,6 @@ make_pass_tree_loop_init (gcc::context *ctxt) return new pass_tree_loop_init (ctxt); } -/* Loop invariant motion pass. */ - -static unsigned int -tree_ssa_loop_im (void) -{ - if (number_of_loops (cfun) <= 1) - return 0; - - return tree_ssa_lim (); -} - -static bool -gate_tree_ssa_loop_im (void) -{ - return flag_tree_loop_im != 0; -} - -namespace { - -const pass_data pass_data_lim = -{ - GIMPLE_PASS, /* type */ - "lim", /* name */ - OPTGROUP_LOOP, /* optinfo_flags */ - true, /* has_gate */ - true, /* has_execute */ - TV_LIM, /* tv_id */ - PROP_cfg, /* properties_required */ - 0, /* properties_provided */ - 0, /* properties_destroyed */ - 0, /* todo_flags_start */ - 0, /* todo_flags_finish */ -}; - -class pass_lim : public gimple_opt_pass -{ -public: - pass_lim (gcc::context *ctxt) - : gimple_opt_pass (pass_data_lim, ctxt) - {} - - /* opt_pass methods: */ - opt_pass * clone () { return new pass_lim (m_ctxt); } - bool gate () { return gate_tree_ssa_loop_im (); } - unsigned int execute () { return tree_ssa_loop_im (); } - -}; // class pass_lim - -} // anon namespace - -gimple_opt_pass * -make_pass_lim (gcc::context *ctxt) -{ - return new pass_lim (ctxt); -} - -/* Loop unswitching pass. */ - -static unsigned int -tree_ssa_loop_unswitch (void) -{ - if (number_of_loops (cfun) <= 1) - return 0; - - return tree_ssa_unswitch_loops (); -} - -static bool -gate_tree_ssa_loop_unswitch (void) -{ - return flag_unswitch_loops != 0; -} - -namespace { - -const pass_data pass_data_tree_unswitch = -{ - GIMPLE_PASS, /* type */ - "unswitch", /* name */ - OPTGROUP_LOOP, /* optinfo_flags */ - true, /* has_gate */ - true, /* has_execute */ - TV_TREE_LOOP_UNSWITCH, /* tv_id */ - PROP_cfg, /* properties_required */ - 0, /* properties_provided */ - 0, /* properties_destroyed */ - 0, /* todo_flags_start */ - 0, /* todo_flags_finish */ -}; - -class pass_tree_unswitch : public gimple_opt_pass -{ -public: - pass_tree_unswitch (gcc::context *ctxt) - : gimple_opt_pass (pass_data_tree_unswitch, ctxt) - {} - - /* opt_pass methods: */ - bool gate () { return gate_tree_ssa_loop_unswitch (); } - unsigned int execute () { return tree_ssa_loop_unswitch (); } - -}; // class pass_tree_unswitch - -} // anon namespace - -gimple_opt_pass * -make_pass_tree_unswitch (gcc::context *ctxt) -{ - return new pass_tree_unswitch (ctxt); -} - /* Predictive commoning. */ static unsigned @@ -515,61 +404,6 @@ make_pass_check_data_deps (gcc::context *ctxt) return new pass_check_data_deps (ctxt); } -/* Canonical induction variable creation pass. */ - -static unsigned int -tree_ssa_loop_ivcanon (void) -{ - if (number_of_loops (cfun) <= 1) - return 0; - - return canonicalize_induction_variables (); -} - -static bool -gate_tree_ssa_loop_ivcanon (void) -{ - return flag_tree_loop_ivcanon != 0; -} - -namespace { - -const pass_data pass_data_iv_canon = -{ - GIMPLE_PASS, /* type */ - "ivcanon", /* name */ - OPTGROUP_LOOP, /* optinfo_flags */ - true, /* has_gate */ - true, /* has_execute */ - TV_TREE_LOOP_IVCANON, /* tv_id */ - ( PROP_cfg | PROP_ssa ), /* properties_required */ - 0, /* properties_provided */ - 0, /* properties_destroyed */ - 0, /* todo_flags_start */ - 0, /* todo_flags_finish */ -}; - -class pass_iv_canon : public gimple_opt_pass -{ -public: - pass_iv_canon (gcc::context *ctxt) - : gimple_opt_pass (pass_data_iv_canon, ctxt) - {} - - /* opt_pass methods: */ - bool gate () { return gate_tree_ssa_loop_ivcanon (); } - unsigned int execute () { return tree_ssa_loop_ivcanon (); } - -}; // class pass_iv_canon - -} // anon namespace - -gimple_opt_pass * -make_pass_iv_canon (gcc::context *ctxt) -{ - return new pass_iv_canon (ctxt); -} - /* Propagation of constants using scev. */ static bool @@ -667,128 +501,6 @@ make_pass_record_bounds (gcc::context *ctxt) return new pass_record_bounds (ctxt); } -/* Complete unrolling of loops. */ - -static unsigned int -tree_complete_unroll (void) -{ - if (number_of_loops (cfun) <= 1) - return 0; - - return tree_unroll_loops_completely (flag_unroll_loops - || flag_peel_loops - || optimize >= 3, true); -} - -static bool -gate_tree_complete_unroll (void) -{ - return true; -} - -namespace { - -const pass_data pass_data_complete_unroll = -{ - GIMPLE_PASS, /* type */ - "cunroll", /* name */ - OPTGROUP_LOOP, /* optinfo_flags */ - true, /* has_gate */ - true, /* has_execute */ - TV_COMPLETE_UNROLL, /* tv_id */ - ( PROP_cfg | PROP_ssa ), /* properties_required */ - 0, /* properties_provided */ - 0, /* properties_destroyed */ - 0, /* todo_flags_start */ - 0, /* todo_flags_finish */ -}; - -class pass_complete_unroll : public gimple_opt_pass -{ -public: - pass_complete_unroll (gcc::context *ctxt) - : gimple_opt_pass (pass_data_complete_unroll, ctxt) - {} - - /* opt_pass methods: */ - bool gate () { return gate_tree_complete_unroll (); } - unsigned int execute () { return tree_complete_unroll (); } - -}; // class pass_complete_unroll - -} // anon namespace - -gimple_opt_pass * -make_pass_complete_unroll (gcc::context *ctxt) -{ - return new pass_complete_unroll (ctxt); -} - -/* Complete unrolling of inner loops. */ - -static unsigned int -tree_complete_unroll_inner (void) -{ - unsigned ret = 0; - - loop_optimizer_init (LOOPS_NORMAL - | LOOPS_HAVE_RECORDED_EXITS); - if (number_of_loops (cfun) > 1) - { - scev_initialize (); - ret = tree_unroll_loops_completely (optimize >= 3, false); - free_numbers_of_iterations_estimates (); - scev_finalize (); - } - loop_optimizer_finalize (); - - return ret; -} - -static bool -gate_tree_complete_unroll_inner (void) -{ - return optimize >= 2; -} - -namespace { - -const pass_data pass_data_complete_unrolli = -{ - GIMPLE_PASS, /* type */ - "cunrolli", /* name */ - OPTGROUP_LOOP, /* optinfo_flags */ - true, /* has_gate */ - true, /* has_execute */ - TV_COMPLETE_UNROLL, /* tv_id */ - ( PROP_cfg | PROP_ssa ), /* properties_required */ - 0, /* properties_provided */ - 0, /* properties_destroyed */ - 0, /* todo_flags_start */ - TODO_verify_flow, /* todo_flags_finish */ -}; - -class pass_complete_unrolli : public gimple_opt_pass -{ -public: - pass_complete_unrolli (gcc::context *ctxt) - : gimple_opt_pass (pass_data_complete_unrolli, ctxt) - {} - - /* opt_pass methods: */ - bool gate () { return gate_tree_complete_unroll_inner (); } - unsigned int execute () { return tree_complete_unroll_inner (); } - -}; // class pass_complete_unrolli - -} // anon namespace - -gimple_opt_pass * -make_pass_complete_unrolli (gcc::context *ctxt) -{ - return new pass_complete_unrolli (ctxt); -} - /* Parallelization. */ static bool @@ -846,61 +558,6 @@ make_pass_parallelize_loops (gcc::context *ctxt) return new pass_parallelize_loops (ctxt); } -/* Prefetching. */ - -static unsigned int -tree_ssa_loop_prefetch (void) -{ - if (number_of_loops (cfun) <= 1) - return 0; - - return tree_ssa_prefetch_arrays (); -} - -static bool -gate_tree_ssa_loop_prefetch (void) -{ - return flag_prefetch_loop_arrays > 0; -} - -namespace { - -const pass_data pass_data_loop_prefetch = -{ - GIMPLE_PASS, /* type */ - "aprefetch", /* name */ - OPTGROUP_LOOP, /* optinfo_flags */ - true, /* has_gate */ - true, /* has_execute */ - TV_TREE_PREFETCH, /* tv_id */ - ( PROP_cfg | PROP_ssa ), /* properties_required */ - 0, /* properties_provided */ - 0, /* properties_destroyed */ - 0, /* todo_flags_start */ - 0, /* todo_flags_finish */ -}; - -class pass_loop_prefetch : public gimple_opt_pass -{ -public: - pass_loop_prefetch (gcc::context *ctxt) - : gimple_opt_pass (pass_data_loop_prefetch, ctxt) - {} - - /* opt_pass methods: */ - bool gate () { return gate_tree_ssa_loop_prefetch (); } - unsigned int execute () { return tree_ssa_loop_prefetch (); } - -}; // class pass_loop_prefetch - -} // anon namespace - -gimple_opt_pass * -make_pass_loop_prefetch (gcc::context *ctxt) -{ - return new pass_loop_prefetch (ctxt); -} - /* Induction variable optimizations. */ static unsigned int @@ -1004,3 +661,235 @@ make_pass_tree_loop_done (gcc::context *ctxt) { return new pass_tree_loop_done (ctxt); } + +/* Calls CBCK for each index in memory reference ADDR_P. There are two + kinds situations handled; in each of these cases, the memory reference + and DATA are passed to the callback: + + Access to an array: ARRAY_{RANGE_}REF (base, index). In this case we also + pass the pointer to the index to the callback. + + Pointer dereference: INDIRECT_REF (addr). In this case we also pass the + pointer to addr to the callback. + + If the callback returns false, the whole search stops and false is returned. + Otherwise the function returns true after traversing through the whole + reference *ADDR_P. */ + +bool +for_each_index (tree *addr_p, bool (*cbck) (tree, tree *, void *), void *data) +{ + tree *nxt, *idx; + + for (; ; addr_p = nxt) + { + switch (TREE_CODE (*addr_p)) + { + case SSA_NAME: + return cbck (*addr_p, addr_p, data); + + case MEM_REF: + nxt = &TREE_OPERAND (*addr_p, 0); + return cbck (*addr_p, nxt, data); + + case BIT_FIELD_REF: + case VIEW_CONVERT_EXPR: + case REALPART_EXPR: + case IMAGPART_EXPR: + nxt = &TREE_OPERAND (*addr_p, 0); + break; + + case COMPONENT_REF: + /* If the component has varying offset, it behaves like index + as well. */ + idx = &TREE_OPERAND (*addr_p, 2); + if (*idx + && !cbck (*addr_p, idx, data)) + return false; + + nxt = &TREE_OPERAND (*addr_p, 0); + break; + + case ARRAY_REF: + case ARRAY_RANGE_REF: + nxt = &TREE_OPERAND (*addr_p, 0); + if (!cbck (*addr_p, &TREE_OPERAND (*addr_p, 1), data)) + return false; + break; + + case VAR_DECL: + case PARM_DECL: + case CONST_DECL: + case STRING_CST: + case RESULT_DECL: + case VECTOR_CST: + case COMPLEX_CST: + case INTEGER_CST: + case REAL_CST: + case FIXED_CST: + case CONSTRUCTOR: + return true; + + case ADDR_EXPR: + gcc_assert (is_gimple_min_invariant (*addr_p)); + return true; + + case TARGET_MEM_REF: + idx = &TMR_BASE (*addr_p); + if (*idx + && !cbck (*addr_p, idx, data)) + return false; + idx = &TMR_INDEX (*addr_p); + if (*idx + && !cbck (*addr_p, idx, data)) + return false; + idx = &TMR_INDEX2 (*addr_p); + if (*idx + && !cbck (*addr_p, idx, data)) + return false; + return true; + + default: + gcc_unreachable (); + } + } +} + + +/* The name and the length of the currently generated variable + for lsm. */ +#define MAX_LSM_NAME_LENGTH 40 +static char lsm_tmp_name[MAX_LSM_NAME_LENGTH + 1]; +static int lsm_tmp_name_length; + +/* Adds S to lsm_tmp_name. */ + +static void +lsm_tmp_name_add (const char *s) +{ + int l = strlen (s) + lsm_tmp_name_length; + if (l > MAX_LSM_NAME_LENGTH) + return; + + strcpy (lsm_tmp_name + lsm_tmp_name_length, s); + lsm_tmp_name_length = l; +} + +/* Stores the name for temporary variable that replaces REF to + lsm_tmp_name. */ + +static void +gen_lsm_tmp_name (tree ref) +{ + const char *name; + + switch (TREE_CODE (ref)) + { + case MEM_REF: + case TARGET_MEM_REF: + gen_lsm_tmp_name (TREE_OPERAND (ref, 0)); + lsm_tmp_name_add ("_"); + break; + + case ADDR_EXPR: + gen_lsm_tmp_name (TREE_OPERAND (ref, 0)); + break; + + case BIT_FIELD_REF: + case VIEW_CONVERT_EXPR: + case ARRAY_RANGE_REF: + gen_lsm_tmp_name (TREE_OPERAND (ref, 0)); + break; + + case REALPART_EXPR: + gen_lsm_tmp_name (TREE_OPERAND (ref, 0)); + lsm_tmp_name_add ("_RE"); + break; + + case IMAGPART_EXPR: + gen_lsm_tmp_name (TREE_OPERAND (ref, 0)); + lsm_tmp_name_add ("_IM"); + break; + + case COMPONENT_REF: + gen_lsm_tmp_name (TREE_OPERAND (ref, 0)); + lsm_tmp_name_add ("_"); + name = get_name (TREE_OPERAND (ref, 1)); + if (!name) + name = "F"; + lsm_tmp_name_add (name); + break; + + case ARRAY_REF: + gen_lsm_tmp_name (TREE_OPERAND (ref, 0)); + lsm_tmp_name_add ("_I"); + break; + + case SSA_NAME: + case VAR_DECL: + case PARM_DECL: + name = get_name (ref); + if (!name) + name = "D"; + lsm_tmp_name_add (name); + break; + + case STRING_CST: + lsm_tmp_name_add ("S"); + break; + + case RESULT_DECL: + lsm_tmp_name_add ("R"); + break; + + case INTEGER_CST: + /* Nothing. */ + break; + + default: + gcc_unreachable (); + } +} + +/* Determines name for temporary variable that replaces REF. + The name is accumulated into the lsm_tmp_name variable. + N is added to the name of the temporary. */ + +char * +get_lsm_tmp_name (tree ref, unsigned n, const char *suffix) +{ + char ns[2]; + + lsm_tmp_name_length = 0; + gen_lsm_tmp_name (ref); + lsm_tmp_name_add ("_lsm"); + if (n < 10) + { + ns[0] = '0' + n; + ns[1] = 0; + lsm_tmp_name_add (ns); + } + return lsm_tmp_name; + if (suffix != NULL) + lsm_tmp_name_add (suffix); +} + +/* Computes an estimated number of insns in LOOP, weighted by WEIGHTS. */ + +unsigned +tree_num_loop_insns (struct loop *loop, eni_weights *weights) +{ + basic_block *body = get_loop_body (loop); + gimple_stmt_iterator gsi; + unsigned size = 0, i; + + for (i = 0; i < loop->num_nodes; i++) + for (gsi = gsi_start_bb (body[i]); !gsi_end_p (gsi); gsi_next (&gsi)) + size += estimate_num_insns (gsi_stmt (gsi), weights); + free (body); + + return size; +} + + + diff --git a/gcc/tree-ssa-loop.h b/gcc/tree-ssa-loop.h new file mode 100644 index 00000000000..1c96d9cee5e --- /dev/null +++ b/gcc/tree-ssa-loop.h @@ -0,0 +1,85 @@ +/* Header file for SSA loop optimizations. + Copyright (C) 2013 Free Software Foundation, Inc. + +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/>. */ + +#ifndef GCC_TREE_SSA_LOOP_H +#define GCC_TREE_SSA_LOOP_H + +#include "tree-ssa-loop-ivopts.h" +#include "tree-ssa-loop-manip.h" +#include "tree-ssa-loop-niter.h" + +/* Affine iv. */ + +typedef struct affine_iv_d +{ + /* Iv = BASE + STEP * i. */ + tree base, step; + + /* True if this iv does not overflow. */ + bool no_overflow; +} affine_iv; + +/* Description of number of iterations of a loop. All the expressions inside + the structure can be evaluated at the end of the loop's preheader + (and due to ssa form, also anywhere inside the body of the loop). */ + +struct tree_niter_desc +{ + tree assumptions; /* The boolean expression. If this expression evaluates + to false, then the other fields in this structure + should not be used; there is no guarantee that they + will be correct. */ + tree may_be_zero; /* The boolean expression. If it evaluates to true, + the loop will exit in the first iteration (i.e. + its latch will not be executed), even if the niter + field says otherwise. */ + tree niter; /* The expression giving the number of iterations of + a loop (provided that assumptions == true and + may_be_zero == false), more precisely the number + of executions of the latch of the loop. */ + double_int max; /* The upper bound on the number of iterations of + the loop. */ + + /* The simplified shape of the exit condition. The loop exits if + CONTROL CMP BOUND is false, where CMP is one of NE_EXPR, + LT_EXPR, or GT_EXPR, and step of CONTROL is positive if CMP is + LE_EXPR and negative if CMP is GE_EXPR. This information is used + by loop unrolling. */ + affine_iv control; + tree bound; + enum tree_code cmp; +}; + +extern bool for_each_index (tree *, bool (*) (tree, tree *, void *), void *); +extern char *get_lsm_tmp_name (tree ref, unsigned n, const char *suffix = NULL); +extern unsigned tree_num_loop_insns (struct loop *, struct eni_weights_d *); + +/* Returns the loop of the statement STMT. */ + +static inline struct loop * +loop_containing_stmt (gimple stmt) +{ + basic_block bb = gimple_bb (stmt); + if (!bb) + return NULL; + + return bb->loop_father; +} + +#endif /* GCC_TREE_SSA_LOOP_H */ |