OSDN Git Service

PR middle-end/17055
[pf3gnuchains/gcc-fork.git] / gcc / cfgloop.h
index e879e52..762c1ff 100644 (file)
@@ -1,5 +1,5 @@
 /* Natural loop functions
-   Copyright (C) 1987, 1997, 1998, 1999, 2000, 2001, 2002, 2003
+   Copyright (C) 1987, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004
    Free Software Foundation, Inc.
 
 This file is part of GCC.
@@ -19,6 +19,13 @@ along with GCC; see the file COPYING.  If not, write to the Free
 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
 02111-1307, USA.  */
 
+#ifndef GCC_CFGLOOP_H
+#define GCC_CFGLOOP_H
+
+#include "basic-block.h"
+/* For rtx_code.  */
+#include "rtl.h"
+
 /* Structure to hold decision about unrolling/peeling.  */
 enum lpt_dec
 {
@@ -36,26 +43,6 @@ struct lpt_decision
   unsigned times;
 };
 
-/* Description of loop for simple loop unrolling.  */
-struct loop_desc
-{
-  int postincr;                /* 1 if increment/decrement is done after loop exit condition.  */
-  rtx stride;          /* Value added to VAR in each iteration.  */
-  rtx var;             /* Loop control variable.  */
-  rtx var_alts;                /* List of definitions of its initial value.  */
-  rtx lim;             /* Expression var is compared with.  */
-  rtx lim_alts;                /* List of definitions of its initial value.  */
-  bool const_iter;      /* True if it iterates constant number of times.  */
-  unsigned HOST_WIDE_INT niter;
-                       /* Number of iterations if it is constant.  */
-  bool may_be_zero;     /* If we cannot determine that the first iteration will pass.  */
-  enum rtx_code cond;  /* Exit condition.  */
-  int neg;             /* Set to 1 if loop ends when condition is satisfied.  */
-  edge out_edge;       /* The exit edge.  */
-  edge in_edge;                /* And the other one.  */
-  int n_branches;      /* Number of branches inside the loop.  */
-};
-
 /* Structure to hold information for each natural loop.  */
 struct loop
 {
@@ -74,11 +61,6 @@ struct loop
   /* For loop unrolling/peeling decision.  */
   struct lpt_decision lpt_decision;
 
-  /* Simple loop description.  */
-  int simple;
-  struct loop_desc desc;
-  int has_desc;
-
   /* Number of loop insns.  */
   unsigned ninsns;
 
@@ -153,16 +135,6 @@ struct loop
   /* The following are currently used by loop.c but they are likely to
      disappear as loop.c is converted to use the CFG.  */
 
-  /* Nonzero if the loop has a NOTE_INSN_LOOP_VTOP.  */
-  rtx vtop;
-
-  /* Nonzero if the loop has a NOTE_INSN_LOOP_CONT.
-     A continue statement will generate a branch to NEXT_INSN (cont).  */
-  rtx cont;
-
-  /* The dominator of cont.  */
-  rtx cont_dominator;
-
   /* The NOTE_INSN_LOOP_BEG.  */
   rtx start;
 
@@ -193,6 +165,20 @@ struct loop
   /* The number of LABEL_REFs on exit_labels for this loop and all
      loops nested inside it.  */
   int exit_count;
+
+  /* The probable number of times the loop is executed at runtime.
+     This is an INTEGER_CST or an expression containing symbolic
+     names.  Don't access this field directly:
+     number_of_iterations_in_loop computes and caches the computed
+     information in this field.  */
+  tree nb_iterations;
+
+  /* Upper bound on number of iterations of a loop.  */
+  struct nb_iter_bound *bounds;
+
+  /* If not NULL, loop has just single exit edge stored here (edges to the
+     EXIT_BLOCK_PTR do not count.  */
+  edge single_exit;
 };
 
 /* Flags for state of loop structure.  */
@@ -200,7 +186,8 @@ enum
 {
   LOOPS_HAVE_PREHEADERS = 1,
   LOOPS_HAVE_SIMPLE_LATCHES = 2,
-  LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS = 4
+  LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS = 4,
+  LOOPS_HAVE_MARKED_SINGLE_EXITS = 8
 };
 
 /* Structure to hold CFG information about natural loops within a function.  */
@@ -227,9 +214,6 @@ struct loops
   /* Information derived from the CFG.  */
   struct cfg
   {
-    /* The bitmap vector of dominators or NULL if not computed.  */
-    dominance_info dom;
-
     /* The ordering of the basic blocks in a depth first search.  */
     int *dfs_order;
 
@@ -245,6 +229,10 @@ struct loops
   int state;
 };
 
+/* The loop tree currently optimized.  */
+
+extern struct loops *current_loops;
+
 /* Flags for loop discovery.  */
 
 #define LOOP_TREE              1       /* Build loop hierarchy tree.  */
@@ -262,9 +250,11 @@ extern void flow_loops_dump (const struct loops *, FILE *,
                             void (*)(const struct loop *, FILE *, int), int);
 extern void flow_loop_dump (const struct loop *, FILE *,
                            void (*)(const struct loop *, FILE *, int), int);
-extern int flow_loop_scan (struct loops *, struct loop *, int);
+extern int flow_loop_scan (struct loop *, int);
 extern void flow_loop_free (struct loop *);
 void mark_irreducible_loops (struct loops *);
+void mark_single_exit_loops (struct loops *);
+extern void create_loop_notes (void);
 
 /* Loop data structure manipulation/querying.  */
 extern void flow_loop_tree_node_add (struct loop *, struct loop *);
@@ -273,12 +263,18 @@ extern bool flow_loop_outside_edge_p (const struct loop *, edge);
 extern bool flow_loop_nested_p (const struct loop *, const struct loop *);
 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);
+extern unsigned tree_num_loop_insns (struct loop *);
 extern int num_loop_insns (struct loop *);
 extern int average_num_loop_insns (struct loop *);
+extern unsigned get_loop_level (const struct loop *);
 
 /* Loops & cfg manipulation.  */
 extern basic_block *get_loop_body (const struct loop *);
+extern basic_block *get_loop_body_in_dom_order (const struct loop *);
+extern basic_block *get_loop_body_in_bfs_order (const struct loop *);
 extern edge *get_loop_exit_edges (const struct loop *, unsigned *);
+extern unsigned num_loop_branches (const struct loop *);
 
 extern edge loop_preheader_edge (const struct loop *);
 extern edge loop_latch_edge (const struct loop *);
@@ -289,7 +285,7 @@ extern void remove_bb_from_loops (basic_block);
 extern void cancel_loop (struct loops *, struct loop *);
 extern void cancel_loop_tree (struct loops *, struct loop *);
 
-extern basic_block loop_split_edge_with (edge, rtx, struct loops *);
+extern basic_block loop_split_edge_with (edge, rtx);
 extern int fix_loop_placement (struct loop *);
 
 enum
@@ -303,10 +299,7 @@ extern void force_single_succ_latches (struct loops *);
 extern void verify_loop_structure (struct loops *);
 
 /* Loop analysis.  */
-extern bool simple_loop_p (struct loops *, struct loop *, struct loop_desc *);
-extern rtx count_loop_iterations (struct loop_desc *, rtx, rtx);
-extern bool just_once_each_iteration_p (struct loops *,struct loop *,
-                                       basic_block);
+extern bool just_once_each_iteration_p (struct loop *, basic_block);
 extern unsigned expected_loop_iterations (const struct loop *);
 
 /* Loop manipulation.  */
@@ -321,7 +314,131 @@ extern int duplicate_loop_to_header_edge (struct loop *, edge, struct loops *,
 extern struct loop *loopify (struct loops *, edge, edge, basic_block);
 extern void unloop (struct loops *, struct loop *);
 extern bool remove_path (struct loops *, edge);
-extern edge split_loop_bb (struct loops *, basic_block, rtx);
+extern edge split_loop_bb (basic_block, rtx);
+
+/* Induction variable analysis.  */
+
+/* The description of induction variable.  The things are a bit complicated
+   due to need to handle subregs and extends.  The value of the object described
+   by it can be obtained as follows (all computations are done in extend_mode):
+
+   Value in i-th iteration is
+     delta + mult * extend_{extend_mode} (subreg_{mode} (base + i * step)).
+
+   If first_special is true, the value in the first iteration is
+     delta + mult * base
+     
+   If extend = UNKNOWN, first_special must be false, delta 0, mult 1 and value is
+     subreg_{mode} (base + i * step)
+
+   The get_iv_value function can be used to obtain these expressions.
+
+   ??? Add a third mode field that would specify the mode in that inner
+   computation is done, which would enable it to be different from the
+   outer one?  */
+
+struct rtx_iv
+{
+  /* Its base and step (mode of base and step is supposed to be extend_mode,
+     see the description above).  */
+  rtx base, step;
+
+  /* The type of extend applied to it (SIGN_EXTEND, ZERO_EXTEND or UNKNOWN).  */
+  enum rtx_code extend;
+
+  /* Operations applied in the extended mode.  */
+  rtx delta, mult;
+
+  /* The mode it is extended to.  */
+  enum machine_mode extend_mode;
+
+  /* The mode the variable iterates in.  */
+  enum machine_mode mode;
+
+  /* Whether we have already filled the remaining fields.  */
+  unsigned analysed : 1;
+
+  /* Whether the first iteration needs to be handled specially.  */
+  unsigned first_special : 1;
+};
+
+/* The description of an exit from the loop and of the number of iterations
+   till we take the exit.  */
+
+struct niter_desc
+{
+  /* The edge out of the loop.  */
+  edge out_edge;
+
+  /* The other edge leading from the condition.  */
+  edge in_edge;
+
+  /* True if we are able to say anything about number of iterations of the
+     loop.  */
+  bool simple_p;
+
+  /* True if the loop iterates the constant number of times.  */
+  bool const_iter;
+
+  /* Number of iterations if constant.  */
+  unsigned HOST_WIDEST_INT niter;
+
+  /* Upper bound on the number of iterations.  */
+  unsigned HOST_WIDEST_INT niter_max;
+
+  /* Assumptions under that the rest of the information is valid.  */
+  rtx assumptions;
+
+  /* Assumptions under that the loop ends before reaching the latch,
+     even if value of niter_expr says otherwise.  */
+  rtx noloop_assumptions;
+
+  /* Condition under that the loop is infinite.  */
+  rtx infinite;
+
+  /* Whether the comparison is signed.  */
+  bool signed_p;
+
+  /* The mode in that niter_expr should be computed.  */
+  enum machine_mode mode;
+
+  /* The number of iterations of the loop.  */
+  rtx niter_expr;
+};
+
+extern void iv_analysis_loop_init (struct loop *);
+extern rtx iv_get_reaching_def (rtx, rtx);
+extern bool iv_analyze (rtx, rtx, struct rtx_iv *);
+extern rtx get_iv_value (struct rtx_iv *, rtx);
+extern void find_simple_exit (struct loop *, struct niter_desc *);
+extern void iv_number_of_iterations (struct loop *, rtx, rtx,
+                                    struct niter_desc *);
+extern void iv_analysis_done (void);
+
+extern struct niter_desc *get_simple_loop_desc (struct loop *loop);
+extern void free_simple_loop_desc (struct loop *loop);
+
+static inline struct niter_desc *
+simple_loop_desc (struct loop *loop)
+{
+  return loop->aux;
+}
+
+/* The properties of the target.  */
+
+extern unsigned target_avail_regs;     /* Number of available registers.  */
+extern unsigned target_res_regs;       /* Number of reserved registers.  */
+extern unsigned target_small_cost;     /* The cost for register when there
+                                          is a free one.  */
+extern unsigned target_pres_cost;      /* The cost for register when there are
+                                          not too many free ones.  */
+extern unsigned target_spill_cost;     /* The cost for register when we need
+                                          to spill.  */
+
+/* Register pressure estimation for induction variable optimizations & loop
+   invariant motion.  */
+extern unsigned global_cost_for_size (unsigned, unsigned, unsigned);
+extern void init_set_costs (void);
 
 /* Loop optimizer initialization.  */
 extern struct loops *loop_optimizer_init (FILE *);
@@ -338,3 +455,7 @@ enum
 };
 
 extern void unroll_and_peel_loops (struct loops *, int);
+extern void doloop_optimize_loops (struct loops *);
+extern void move_loop_invariants (struct loops *);
+
+#endif /* GCC_CFGLOOP_H */