gcc/cfgloop.h

   1 /* Natural loop functions
   2    Copyright (C) 1987, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005
   3    Free Software Foundation, Inc.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 2, or (at your option) any later
  10 version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING.  If not, write to the Free
  19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
  20 02110-1301, USA.  */
  21
  22 #ifndef GCC_CFGLOOP_H
  23 #define GCC_CFGLOOP_H
  24
  25 #include "basic-block.h"
  26 /* For rtx_code.  */
  27 #include "rtl.h"
  28
  29 /* Structure to hold decision about unrolling/peeling.  */
  30 enum lpt_dec
  31 {
  32   LPT_NONE,
  33   LPT_PEEL_COMPLETELY,
  34   LPT_PEEL_SIMPLE,
  35   LPT_UNROLL_CONSTANT,
  36   LPT_UNROLL_RUNTIME,
  37   LPT_UNROLL_STUPID
  38 };
  39
  40 struct lpt_decision
  41 {
  42   enum lpt_dec decision;
  43   unsigned times;
  44 };
  45
  46 /* The structure describing a bound on number of iterations of a loop.  */
  47
  48 struct nb_iter_bound
  49 {
  50   /* The statement STMT is executed at most ...  */
  51   tree stmt;
  52
  53   /* ... BOUND + 1 times (BOUND must be an unsigned constant).
  54      The + 1 is added for the following reasons:
  55
  56      a) 0 would otherwise be unused, while we would need to care more about
  57         overflows (as MAX + 1 is sometimes produced as the estimate on number
  58         of executions of STMT).
  59      b) it is consistent with the result of number_of_iterations_exit.  */
  60   double_int bound;
  61
  62   /* True if the statement will cause the loop to be leaved the (at most)
  63      BOUND + 1-st time it is executed, that is, all the statements after it
  64      are executed at most BOUND times.  */
  65   bool is_exit;
  66
  67   /* True if the bound is "realistic" -- i.e., most likely the loop really has
  68      number of iterations close to the bound.  Exact bounds (if the number of
  69      iterations of a loop is a constant) and bounds derived from the size of
  70      data accessed in the loop are considered realistic.  */
  71   bool realistic;
  72
  73   /* The next bound in the list.  */
  74   struct nb_iter_bound *next;
  75 };
  76
  77 /* Structure to hold information for each natural loop.  */
  78 struct loop
  79 {
  80   /* Index into loops array.  */
  81   int num;
  82
  83   /* Basic block of loop header.  */
  84   basic_block header;
  85
  86   /* Basic block of loop latch.  */
  87   basic_block latch;
  88
  89   /* For loop unrolling/peeling decision.  */
  90   struct lpt_decision lpt_decision;
  91
  92   /* Number of loop insns.  */
  93   unsigned ninsns;
  94
  95   /* Average number of executed insns per iteration.  */
  96   unsigned av_ninsns;
  97
  98   /* Number of blocks contained within the loop.  */
  99   unsigned num_nodes;
 100
 101   /* The loop nesting depth.  */
 102   int depth;
 103
 104   /* Superloops of the loop.  */
 105   struct loop **pred;
 106
 107   /* The height of the loop (enclosed loop levels) within the loop
 108      hierarchy tree.  */
 109   int level;
 110
 111   /* The outer (parent) loop or NULL if outermost loop.  */
 112   struct loop *outer;
 113
 114   /* The first inner (child) loop or NULL if innermost loop.  */
 115   struct loop *inner;
 116
 117   /* Link to the next (sibling) loop.  */
 118   struct loop *next;
 119
 120   /* Loop that is copy of this loop.  */
 121   struct loop *copy;
 122
 123   /* Auxiliary info specific to a pass.  */
 124   void *aux;
 125
 126   /* The probable number of times the loop is executed at runtime.
 127      This is an INTEGER_CST or an expression containing symbolic
 128      names.  Don't access this field directly:
 129      number_of_iterations_in_loop computes and caches the computed
 130      information in this field.  */
 131   tree nb_iterations;
 132
 133   /* An integer estimation of the number of iterations.  Estimate_state
 134      describes what is the state of the estimation.  */
 135   enum
 136     {
 137       /* Estimate was not computed yet.  */
 138       EST_NOT_COMPUTED,
 139       /* Estimate was computed, but we could derive no useful bound.  */
 140       EST_NOT_AVAILABLE,
 141       /* Estimate is ready.  */
 142       EST_AVAILABLE
 143     } estimate_state;
 144   double_int estimated_nb_iterations;
 145
 146   /* Upper bound on number of iterations of a loop.  */
 147   struct nb_iter_bound *bounds;
 148
 149   /* If not NULL, loop has just single exit edge stored here (edges to the
 150      EXIT_BLOCK_PTR do not count.  */
 151   edge single_exit;
 152
 153   /* True when the loop does not carry data dependences, and
 154      consequently the iterations can be executed in any order.  False
 155      when the loop carries data dependences, or when the property is
 156      not decidable.  */
 157   bool parallel_p;
 158 };
 159
 160 /* Flags for state of loop structure.  */
 161 enum
 162 {
 163   LOOPS_HAVE_PREHEADERS = 1,
 164   LOOPS_HAVE_SIMPLE_LATCHES = 2,
 165   LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS = 4,
 166   LOOPS_HAVE_MARKED_SINGLE_EXITS = 8
 167 };
 168
 169 #define LOOPS_NORMAL (LOOPS_HAVE_PREHEADERS | LOOPS_HAVE_SIMPLE_LATCHES \
 170                       | LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)
 171
 172 /* Structure to hold CFG information about natural loops within a function.  */
 173 struct loops
 174 {
 175   /* Number of natural loops in the function.  */
 176   unsigned num;
 177
 178   /* State of loops.  */
 179   int state;
 180
 181   /* We store just pointers to loops here.
 182      Note that a loop in this array may actually be NULL, if the loop
 183      has been removed and the entire loops structure has not been
 184      recomputed since that time.  */
 185   struct loop **parray;
 186
 187   /* Pointer to root of loop hierarchy tree.  */
 188   struct loop *tree_root;
 189
 190   /* Headers shared by multiple loops that should be merged.  */
 191   sbitmap shared_headers;
 192 };
 193
 194 /* Loop recognition.  */
 195 extern int flow_loops_find (struct loops *);
 196 extern void flow_loops_free (struct loops *);
 197 extern void flow_loops_dump (const struct loops *, FILE *,
 198                              void (*)(const struct loop *, FILE *, int), int);
 199 extern void flow_loop_dump (const struct loop *, FILE *,
 200                             void (*)(const struct loop *, FILE *, int), int);
 201 extern void flow_loop_free (struct loop *);
 202 int flow_loop_nodes_find (basic_block, struct loop *);
 203 void fix_loop_structure (struct loops *, bitmap changed_bbs);
 204 void mark_irreducible_loops (struct loops *);
 205 void mark_single_exit_loops (struct loops *);
 206
 207 /* Loop data structure manipulation/querying.  */
 208 extern void flow_loop_tree_node_add (struct loop *, struct loop *);
 209 extern void flow_loop_tree_node_remove (struct loop *);
 210 extern bool flow_loop_nested_p  (const struct loop *, const struct loop *);
 211 extern bool flow_bb_inside_loop_p (const struct loop *, const basic_block);
 212 extern struct loop * find_common_loop (struct loop *, struct loop *);
 213 struct loop *superloop_at_depth (struct loop *, unsigned);
 214 extern unsigned tree_num_loop_insns (struct loop *);
 215 extern int num_loop_insns (struct loop *);
 216 extern int average_num_loop_insns (struct loop *);
 217 extern unsigned get_loop_level (const struct loop *);
 218 extern bool loop_exit_edge_p (const struct loop *, edge);
 219 extern void mark_loop_exit_edges (struct loops *);
 220
 221 /* Loops & cfg manipulation.  */
 222 extern basic_block *get_loop_body (const struct loop *);
 223 extern basic_block *get_loop_body_in_dom_order (const struct loop *);
 224 extern basic_block *get_loop_body_in_bfs_order (const struct loop *);
 225 extern edge *get_loop_exit_edges (const struct loop *, unsigned *);
 226 extern unsigned num_loop_branches (const struct loop *);
 227
 228 extern edge loop_preheader_edge (const struct loop *);
 229 extern edge loop_latch_edge (const struct loop *);
 230
 231 extern void add_bb_to_loop (basic_block, struct loop *);
 232 extern void remove_bb_from_loops (basic_block);
 233
 234 extern void cancel_loop_tree (struct loops *, struct loop *);
 235
 236 extern int fix_loop_placement (struct loop *);
 237
 238 enum
 239 {
 240   CP_SIMPLE_PREHEADERS = 1
 241 };
 242
 243 extern void create_preheaders (struct loops *, int);
 244 extern void force_single_succ_latches (struct loops *);
 245
 246 extern void verify_loop_structure (struct loops *);
 247
 248 /* Loop analysis.  */
 249 extern bool just_once_each_iteration_p (const struct loop *, basic_block);
 250 extern unsigned expected_loop_iterations (const struct loop *);
 251 extern rtx doloop_condition_get (rtx);
 252
 253 /* Loop manipulation.  */
 254 extern bool can_duplicate_loop_p (struct loop *loop);
 255
 256 #define DLTHE_FLAG_UPDATE_FREQ  1       /* Update frequencies in
 257                                            duplicate_loop_to_header_edge.  */
 258 #define DLTHE_RECORD_COPY_NUMBER 2      /* Record copy number in the aux
 259                                            field of newly create BB.  */
 260 #define DLTHE_FLAG_COMPLETTE_PEEL 4     /* Update frequencies expecting
 261                                            a complete peeling.  */
 262
 263 extern struct loop * duplicate_loop (struct loops *, struct loop *,
 264                                      struct loop *);
 265 extern bool duplicate_loop_to_header_edge (struct loop *, edge, struct loops *,
 266                                            unsigned, sbitmap, edge, edge *,
 267                                            unsigned *, int);
 268 extern struct loop *loopify (struct loops *, edge, edge,
 269                              basic_block, edge, edge, bool);
 270 struct loop * loop_version (struct loops *, struct loop *, void *,
 271                             basic_block *, bool);
 272 extern bool remove_path (struct loops *, edge);
 273
 274 /* Induction variable analysis.  */
 275
 276 /* The description of induction variable.  The things are a bit complicated
 277    due to need to handle subregs and extends.  The value of the object described
 278    by it can be obtained as follows (all computations are done in extend_mode):
 279
 280    Value in i-th iteration is
 281      delta + mult * extend_{extend_mode} (subreg_{mode} (base + i * step)).
 282
 283    If first_special is true, the value in the first iteration is
 284      delta + mult * base
 285
 286    If extend = UNKNOWN, first_special must be false, delta 0, mult 1 and value is
 287      subreg_{mode} (base + i * step)
 288
 289    The get_iv_value function can be used to obtain these expressions.
 290
 291    ??? Add a third mode field that would specify the mode in that inner
 292    computation is done, which would enable it to be different from the
 293    outer one?  */
 294
 295 struct rtx_iv
 296 {
 297   /* Its base and step (mode of base and step is supposed to be extend_mode,
 298      see the description above).  */
 299   rtx base, step;
 300
 301   /* The type of extend applied to it (SIGN_EXTEND, ZERO_EXTEND or UNKNOWN).  */
 302   enum rtx_code extend;
 303
 304   /* Operations applied in the extended mode.  */
 305   rtx delta, mult;
 306
 307   /* The mode it is extended to.  */
 308   enum machine_mode extend_mode;
 309
 310   /* The mode the variable iterates in.  */
 311   enum machine_mode mode;
 312
 313   /* Whether the first iteration needs to be handled specially.  */
 314   unsigned first_special : 1;
 315 };
 316
 317 /* The description of an exit from the loop and of the number of iterations
 318    till we take the exit.  */
 319
 320 struct niter_desc
 321 {
 322   /* The edge out of the loop.  */
 323   edge out_edge;
 324
 325   /* The other edge leading from the condition.  */
 326   edge in_edge;
 327
 328   /* True if we are able to say anything about number of iterations of the
 329      loop.  */
 330   bool simple_p;
 331
 332   /* True if the loop iterates the constant number of times.  */
 333   bool const_iter;
 334
 335   /* Number of iterations if constant.  */
 336   unsigned HOST_WIDEST_INT niter;
 337
 338   /* Upper bound on the number of iterations.  */
 339   unsigned HOST_WIDEST_INT niter_max;
 340
 341   /* Assumptions under that the rest of the information is valid.  */
 342   rtx assumptions;
 343
 344   /* Assumptions under that the loop ends before reaching the latch,
 345      even if value of niter_expr says otherwise.  */
 346   rtx noloop_assumptions;
 347
 348   /* Condition under that the loop is infinite.  */
 349   rtx infinite;
 350
 351   /* Whether the comparison is signed.  */
 352   bool signed_p;
 353
 354   /* The mode in that niter_expr should be computed.  */
 355   enum machine_mode mode;
 356
 357   /* The number of iterations of the loop.  */
 358   rtx niter_expr;
 359 };
 360
 361 extern void iv_analysis_loop_init (struct loop *);
 362 extern bool iv_analyze (rtx, rtx, struct rtx_iv *);
 363 extern bool iv_analyze_result (rtx, rtx, struct rtx_iv *);
 364 extern bool iv_analyze_expr (rtx, rtx, enum machine_mode, struct rtx_iv *);
 365 extern rtx get_iv_value (struct rtx_iv *, rtx);
 366 extern bool biv_p (rtx, rtx);
 367 extern void find_simple_exit (struct loop *, struct niter_desc *);
 368 extern void iv_analysis_done (void);
 369 extern struct df *iv_current_loop_df (void);
 370
 371 extern struct niter_desc *get_simple_loop_desc (struct loop *loop);
 372 extern void free_simple_loop_desc (struct loop *loop);
 373
 374 static inline struct niter_desc *
 375 simple_loop_desc (struct loop *loop)
 376 {
 377   return (struct niter_desc *) loop->aux;
 378 }
 379
 380 /* The properties of the target.  */
 381
 382 extern unsigned target_avail_regs;      /* Number of available registers.  */
 383 extern unsigned target_res_regs;        /* Number of reserved registers.  */
 384 extern unsigned target_small_cost;      /* The cost for register when there
 385                                            is a free one.  */
 386 extern unsigned target_pres_cost;       /* The cost for register when there are
 387                                            not too many free ones.  */
 388 extern unsigned target_spill_cost;      /* The cost for register when we need
 389                                            to spill.  */
 390
 391 /* Register pressure estimation for induction variable optimizations & loop
 392    invariant motion.  */
 393 extern unsigned global_cost_for_size (unsigned, unsigned, unsigned);
 394 extern void init_set_costs (void);
 395
 396 /* Loop optimizer initialization.  */
 397 extern void loop_optimizer_init (unsigned);
 398 extern void loop_optimizer_finalize (void);
 399
 400 /* Optimization passes.  */
 401 extern void unswitch_loops (struct loops *);
 402
 403 enum
 404 {
 405   UAP_PEEL = 1,         /* Enables loop peeling.  */
 406   UAP_UNROLL = 2,       /* Enables unrolling of loops if it seems profitable.  */
 407   UAP_UNROLL_ALL = 4    /* Enables unrolling of all loops.  */
 408 };
 409
 410 extern void unroll_and_peel_loops (struct loops *, int);
 411 extern void doloop_optimize_loops (struct loops *);
 412 extern void move_loop_invariants (struct loops *);
 413
 414 #endif /* GCC_CFGLOOP_H */