gcc/cfgloop.h

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