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 #include "vecprim.h"
  29
  30 /* Structure to hold decision about unrolling/peeling.  */
  31 enum lpt_dec
  32 {
  33   LPT_NONE,
  34   LPT_PEEL_COMPLETELY,
  35   LPT_PEEL_SIMPLE,
  36   LPT_UNROLL_CONSTANT,
  37   LPT_UNROLL_RUNTIME,
  38   LPT_UNROLL_STUPID
  39 };
  40
  41 struct lpt_decision
  42 {
  43   enum lpt_dec decision;
  44   unsigned times;
  45 };
  46
  47 /* The structure describing a bound on number of iterations of a loop.  */
  48
  49 struct nb_iter_bound
  50 {
  51   /* The statement STMT is executed at most ...  */
  52   tree stmt;
  53
  54   /* ... BOUND + 1 times (BOUND must be an unsigned constant).
  55      The + 1 is added for the following reasons:
  56
  57      a) 0 would otherwise be unused, while we would need to care more about
  58         overflows (as MAX + 1 is sometimes produced as the estimate on number
  59         of executions of STMT).
  60      b) it is consistent with the result of number_of_iterations_exit.  */
  61   double_int bound;
  62
  63   /* True if the statement will cause the loop to be leaved the (at most)
  64      BOUND + 1-st time it is executed, that is, all the statements after it
  65      are executed at most BOUND times.  */
  66   bool is_exit;
  67
  68   /* True if the bound is "realistic" -- i.e., most likely the loop really has
  69      number of iterations close to the bound.  Exact bounds (if the number of
  70      iterations of a loop is a constant) and bounds derived from the size of
  71      data accessed in the loop are considered realistic.  */
  72   bool realistic;
  73
  74   /* The next bound in the list.  */
  75   struct nb_iter_bound *next;
  76 };
  77
  78 /* Description of the loop exit.  */
  79
  80 struct loop_exit
  81 {
  82   /* The exit edge.  */
  83   edge e;
  84
  85   /* Previous and next exit in the list of the exits of the loop.  */
  86   struct loop_exit *prev;
  87   struct loop_exit *next;
  88
  89   /* Next element in the list of loops from that E exits.  */
  90   struct loop_exit *next_e;
  91 };
  92
  93 /* Structure to hold information for each natural loop.  */
  94 struct loop
  95 {
  96   /* Index into loops array.  */
  97   int num;
  98
  99   /* Basic block of loop header.  */
 100   basic_block header;
 101
 102   /* Basic block of loop latch.  */
 103   basic_block latch;
 104
 105   /* For loop unrolling/peeling decision.  */
 106   struct lpt_decision lpt_decision;
 107
 108   /* Number of loop insns.  */
 109   unsigned ninsns;
 110
 111   /* Average number of executed insns per iteration.  */
 112   unsigned av_ninsns;
 113
 114   /* Number of blocks contained within the loop.  */
 115   unsigned num_nodes;
 116
 117   /* The loop nesting depth.  */
 118   int depth;
 119
 120   /* Superloops of the loop.  */
 121   struct loop **pred;
 122
 123   /* The outer (parent) loop or NULL if outermost loop.  */
 124   struct loop *outer;
 125
 126   /* The first inner (child) loop or NULL if innermost loop.  */
 127   struct loop *inner;
 128
 129   /* Link to the next (sibling) loop.  */
 130   struct loop *next;
 131
 132   /* Loop that is copy of this loop.  */
 133   struct loop *copy;
 134
 135   /* Auxiliary info specific to a pass.  */
 136   void *aux;
 137
 138   /* The number of times the latch of the loop is executed.
 139      This is an INTEGER_CST or an expression containing symbolic
 140      names.  Don't access this field directly:
 141      number_of_latch_executions computes and caches the computed
 142      information in this field.  */
 143   tree nb_iterations;
 144
 145   /* An integer estimation of the number of iterations.  Estimate_state
 146      describes what is the state of the estimation.  */
 147   enum
 148     {
 149       /* Estimate was not computed yet.  */
 150       EST_NOT_COMPUTED,
 151       /* Estimate was computed, but we could derive no useful bound.  */
 152       EST_NOT_AVAILABLE,
 153       /* Estimate is ready.  */
 154       EST_AVAILABLE
 155     } estimate_state;
 156   double_int estimated_nb_iterations;
 157
 158   /* Upper bound on number of iterations of a loop.  */
 159   struct nb_iter_bound *bounds;
 160
 161   /* Head of the cyclic list of the exits of the loop.  */
 162   struct loop_exit exits;
 163 };
 164
 165 /* Flags for state of loop structure.  */
 166 enum
 167 {
 168   LOOPS_HAVE_PREHEADERS = 1,
 169   LOOPS_HAVE_SIMPLE_LATCHES = 2,
 170   LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS = 4,
 171   LOOPS_HAVE_RECORDED_EXITS = 8,
 172   LOOPS_MAY_HAVE_MULTIPLE_LATCHES = 16
 173 };
 174
 175 #define LOOPS_NORMAL (LOOPS_HAVE_PREHEADERS | LOOPS_HAVE_SIMPLE_LATCHES \
 176                       | LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)
 177 #define AVOID_CFG_MODIFICATIONS (LOOPS_MAY_HAVE_MULTIPLE_LATCHES)
 178
 179 typedef struct loop *loop_p;
 180 DEF_VEC_P (loop_p);
 181 DEF_VEC_ALLOC_P (loop_p, heap);
 182
 183 /* Structure to hold CFG information about natural loops within a function.  */
 184 struct loops
 185 {
 186   /* State of loops.  */
 187   int state;
 188
 189   /* Array of the loops.  */
 190   VEC (loop_p, heap) *larray;
 191
 192   /* Maps edges to the list of their descriptions as loop exits.  Edges
 193      whose sources or destinations have loop_father == NULL (which may
 194      happen during the cfg manipulations) should not appear in EXITS.  */
 195   htab_t exits;
 196
 197   /* Pointer to root of loop hierarchy tree.  */
 198   struct loop *tree_root;
 199 };
 200
 201 /* Loop recognition.  */
 202 extern int flow_loops_find (struct loops *);
 203 extern void disambiguate_loops_with_multiple_latches (void);
 204 extern void flow_loops_free (struct loops *);
 205 extern void flow_loops_dump (FILE *,
 206                              void (*)(const struct loop *, FILE *, int), int);
 207 extern void flow_loop_dump (const struct loop *, FILE *,
 208                             void (*)(const struct loop *, FILE *, int), int);
 209 struct loop *alloc_loop (void);
 210 extern void flow_loop_free (struct loop *);
 211 int flow_loop_nodes_find (basic_block, struct loop *);
 212 void fix_loop_structure (bitmap changed_bbs);
 213 void mark_irreducible_loops (void);
 214 void release_recorded_exits (void);
 215 void record_loop_exits (void);
 216 void rescan_loop_exit (edge, bool, bool);
 217
 218 /* Loop data structure manipulation/querying.  */
 219 extern void flow_loop_tree_node_add (struct loop *, struct loop *);
 220 extern void flow_loop_tree_node_remove (struct loop *);
 221 extern void add_loop (struct loop *, struct loop *);
 222 extern bool flow_loop_nested_p  (const struct loop *, const struct loop *);
 223 extern bool flow_bb_inside_loop_p (const struct loop *, const basic_block);
 224 extern struct loop * find_common_loop (struct loop *, struct loop *);
 225 struct loop *superloop_at_depth (struct loop *, unsigned);
 226 struct eni_weights_d;
 227 extern unsigned tree_num_loop_insns (struct loop *, struct eni_weights_d *);
 228 extern int num_loop_insns (struct loop *);
 229 extern int average_num_loop_insns (struct loop *);
 230 extern unsigned get_loop_level (const struct loop *);
 231 extern bool loop_exit_edge_p (const struct loop *, edge);
 232 extern void mark_loop_exit_edges (void);
 233
 234 /* Loops & cfg manipulation.  */
 235 extern basic_block *get_loop_body (const struct loop *);
 236 extern unsigned get_loop_body_with_size (const struct loop *, basic_block *,
 237                                          unsigned);
 238 extern basic_block *get_loop_body_in_dom_order (const struct loop *);
 239 extern basic_block *get_loop_body_in_bfs_order (const struct loop *);
 240 extern VEC (edge, heap) *get_loop_exit_edges (const struct loop *);
 241 edge single_exit (const struct loop *);
 242 extern unsigned num_loop_branches (const struct loop *);
 243
 244 extern edge loop_preheader_edge (const struct loop *);
 245 extern edge loop_latch_edge (const struct loop *);
 246
 247 extern void add_bb_to_loop (basic_block, struct loop *);
 248 extern void remove_bb_from_loops (basic_block);
 249
 250 extern void cancel_loop_tree (struct loop *);
 251 extern void delete_loop (struct loop *);
 252
 253 enum
 254 {
 255   CP_SIMPLE_PREHEADERS = 1
 256 };
 257
 258 extern void create_preheaders (int);
 259 extern void force_single_succ_latches (void);
 260
 261 extern void verify_loop_structure (void);
 262
 263 /* Loop analysis.  */
 264 extern bool just_once_each_iteration_p (const struct loop *, basic_block);
 265 extern unsigned expected_loop_iterations (const struct loop *);
 266 extern rtx doloop_condition_get (rtx);
 267
 268 /* Loop manipulation.  */
 269 extern bool can_duplicate_loop_p (struct loop *loop);
 270
 271 #define DLTHE_FLAG_UPDATE_FREQ  1       /* Update frequencies in
 272                                            duplicate_loop_to_header_edge.  */
 273 #define DLTHE_RECORD_COPY_NUMBER 2      /* Record copy number in the aux
 274                                            field of newly create BB.  */
 275 #define DLTHE_FLAG_COMPLETTE_PEEL 4     /* Update frequencies expecting
 276                                            a complete peeling.  */
 277
 278 extern struct loop * duplicate_loop (struct loop *, struct loop *);
 279 extern bool duplicate_loop_to_header_edge (struct loop *, edge,
 280                                            unsigned, sbitmap, edge,
 281                                            VEC (edge, heap) **, int);
 282 extern struct loop *loopify (edge, edge,
 283                              basic_block, edge, edge, bool,
 284                              unsigned, unsigned);
 285 struct loop * loop_version (struct loop *, void *,
 286                             basic_block *, unsigned, unsigned, unsigned, bool);
 287 extern bool remove_path (edge);
 288 void scale_loop_frequencies (struct loop *, int, int);
 289
 290 /* Induction variable analysis.  */
 291
 292 /* The description of induction variable.  The things are a bit complicated
 293    due to need to handle subregs and extends.  The value of the object described
 294    by it can be obtained as follows (all computations are done in extend_mode):
 295
 296    Value in i-th iteration is
 297      delta + mult * extend_{extend_mode} (subreg_{mode} (base + i * step)).
 298
 299    If first_special is true, the value in the first iteration is
 300      delta + mult * base
 301
 302    If extend = UNKNOWN, first_special must be false, delta 0, mult 1 and value is
 303      subreg_{mode} (base + i * step)
 304
 305    The get_iv_value function can be used to obtain these expressions.
 306
 307    ??? Add a third mode field that would specify the mode in that inner
 308    computation is done, which would enable it to be different from the
 309    outer one?  */
 310
 311 struct rtx_iv
 312 {
 313   /* Its base and step (mode of base and step is supposed to be extend_mode,
 314      see the description above).  */
 315   rtx base, step;
 316
 317   /* The type of extend applied to it (SIGN_EXTEND, ZERO_EXTEND or UNKNOWN).  */
 318   enum rtx_code extend;
 319
 320   /* Operations applied in the extended mode.  */
 321   rtx delta, mult;
 322
 323   /* The mode it is extended to.  */
 324   enum machine_mode extend_mode;
 325
 326   /* The mode the variable iterates in.  */
 327   enum machine_mode mode;
 328
 329   /* Whether the first iteration needs to be handled specially.  */
 330   unsigned first_special : 1;
 331 };
 332
 333 /* The description of an exit from the loop and of the number of iterations
 334    till we take the exit.  */
 335
 336 struct niter_desc
 337 {
 338   /* The edge out of the loop.  */
 339   edge out_edge;
 340
 341   /* The other edge leading from the condition.  */
 342   edge in_edge;
 343
 344   /* True if we are able to say anything about number of iterations of the
 345      loop.  */
 346   bool simple_p;
 347
 348   /* True if the loop iterates the constant number of times.  */
 349   bool const_iter;
 350
 351   /* Number of iterations if constant.  */
 352   unsigned HOST_WIDEST_INT niter;
 353
 354   /* Upper bound on the number of iterations.  */
 355   unsigned HOST_WIDEST_INT niter_max;
 356
 357   /* Assumptions under that the rest of the information is valid.  */
 358   rtx assumptions;
 359
 360   /* Assumptions under that the loop ends before reaching the latch,
 361      even if value of niter_expr says otherwise.  */
 362   rtx noloop_assumptions;
 363
 364   /* Condition under that the loop is infinite.  */
 365   rtx infinite;
 366
 367   /* Whether the comparison is signed.  */
 368   bool signed_p;
 369
 370   /* The mode in that niter_expr should be computed.  */
 371   enum machine_mode mode;
 372
 373   /* The number of iterations of the loop.  */
 374   rtx niter_expr;
 375 };
 376
 377 extern void iv_analysis_loop_init (struct loop *);
 378 extern bool iv_analyze (rtx, rtx, struct rtx_iv *);
 379 extern bool iv_analyze_result (rtx, rtx, struct rtx_iv *);
 380 extern bool iv_analyze_expr (rtx, rtx, enum machine_mode, struct rtx_iv *);
 381 extern rtx get_iv_value (struct rtx_iv *, rtx);
 382 extern bool biv_p (rtx, rtx);
 383 extern void find_simple_exit (struct loop *, struct niter_desc *);
 384 extern void iv_analysis_done (void);
 385 extern struct df *iv_current_loop_df (void);
 386
 387 extern struct niter_desc *get_simple_loop_desc (struct loop *loop);
 388 extern void free_simple_loop_desc (struct loop *loop);
 389
 390 static inline struct niter_desc *
 391 simple_loop_desc (struct loop *loop)
 392 {
 393   return (struct niter_desc *) loop->aux;
 394 }
 395
 396 /* Accessors for the loop structures.  */
 397
 398 /* Returns the loop with index NUM from current_loops.  */
 399
 400 static inline struct loop *
 401 get_loop (unsigned num)
 402 {
 403   return VEC_index (loop_p, current_loops->larray, num);
 404 }
 405
 406 /* Returns the list of loops in current_loops.  */
 407
 408 static inline VEC (loop_p, heap) *
 409 get_loops (void)
 410 {
 411   if (!current_loops)
 412     return NULL;
 413
 414   return current_loops->larray;
 415 }
 416
 417 /* Returns the number of loops in current_loops (including the removed
 418    ones and the fake loop that forms the root of the loop tree).  */
 419
 420 static inline unsigned
 421 number_of_loops (void)
 422 {
 423   if (!current_loops)
 424     return 0;
 425
 426   return VEC_length (loop_p, current_loops->larray);
 427 }
 428
 429 /* Loop iterators.  */
 430
 431 /* Flags for loop iteration.  */
 432
 433 enum li_flags
 434 {
 435   LI_INCLUDE_ROOT = 1,          /* Include the fake root of the loop tree.  */
 436   LI_FROM_INNERMOST = 2,        /* Iterate over the loops in the reverse order,
 437                                    starting from innermost ones.  */
 438   LI_ONLY_INNERMOST = 4         /* Iterate only over innermost loops.  */
 439 };
 440
 441 /* The iterator for loops.  */
 442
 443 typedef struct
 444 {
 445   /* The list of loops to visit.  */
 446   VEC(int,heap) *to_visit;
 447
 448   /* The index of the actual loop.  */
 449   unsigned idx;
 450 } loop_iterator;
 451
 452 static inline void
 453 fel_next (loop_iterator *li, loop_p *loop)
 454 {
 455   int anum;
 456
 457   while (VEC_iterate (int, li->to_visit, li->idx, anum))
 458     {
 459       li->idx++;
 460       *loop = get_loop (anum);
 461       if (*loop)
 462         return;
 463     }
 464
 465   VEC_free (int, heap, li->to_visit);
 466   *loop = NULL;
 467 }
 468
 469 static inline void
 470 fel_init (loop_iterator *li, loop_p *loop, unsigned flags)
 471 {
 472   struct loop *aloop;
 473   unsigned i;
 474   int mn;
 475
 476   li->idx = 0;
 477   if (!current_loops)
 478     {
 479       li->to_visit = NULL;
 480       *loop = NULL;
 481       return;
 482     }
 483
 484   li->to_visit = VEC_alloc (int, heap, number_of_loops ());
 485   mn = (flags & LI_INCLUDE_ROOT) ? 0 : 1;
 486
 487   if (flags & LI_ONLY_INNERMOST)
 488     {
 489       for (i = 0; VEC_iterate (loop_p, current_loops->larray, i, aloop); i++)
 490         if (aloop != NULL
 491             && aloop->inner == NULL
 492             && aloop->num >= mn)
 493           VEC_quick_push (int, li->to_visit, aloop->num);
 494     }
 495   else if (flags & LI_FROM_INNERMOST)
 496     {
 497       /* Push the loops to LI->TO_VISIT in postorder.  */
 498       for (aloop = current_loops->tree_root;
 499            aloop->inner != NULL;
 500            aloop = aloop->inner)
 501         continue;
 502
 503       while (1)
 504         {
 505           if (aloop->num >= mn)
 506             VEC_quick_push (int, li->to_visit, aloop->num);
 507
 508           if (aloop->next)
 509             {
 510               for (aloop = aloop->next;
 511                    aloop->inner != NULL;
 512                    aloop = aloop->inner)
 513                 continue;
 514             }
 515           else if (!aloop->outer)
 516             break;
 517           else
 518             aloop = aloop->outer;
 519         }
 520     }
 521   else
 522     {
 523       /* Push the loops to LI->TO_VISIT in preorder.  */
 524       aloop = current_loops->tree_root;
 525       while (1)
 526         {
 527           if (aloop->num >= mn)
 528             VEC_quick_push (int, li->to_visit, aloop->num);
 529
 530           if (aloop->inner != NULL)
 531             aloop = aloop->inner;
 532           else
 533             {
 534               while (aloop != NULL && aloop->next == NULL)
 535                 aloop = aloop->outer;
 536               if (aloop == NULL)
 537                 break;
 538               aloop = aloop->next;
 539             }
 540         }
 541     }
 542
 543   fel_next (li, loop);
 544 }
 545
 546 #define FOR_EACH_LOOP(LI, LOOP, FLAGS) \
 547   for (fel_init (&(LI), &(LOOP), FLAGS); \
 548        (LOOP); \
 549        fel_next (&(LI), &(LOOP)))
 550
 551 #define FOR_EACH_LOOP_BREAK(LI) \
 552   { \
 553     VEC_free (int, heap, (LI)->to_visit); \
 554     break; \
 555   }
 556
 557 /* The properties of the target.  */
 558
 559 extern unsigned target_avail_regs;      /* Number of available registers.  */
 560 extern unsigned target_res_regs;        /* Number of reserved registers.  */
 561 extern unsigned target_small_cost;      /* The cost for register when there
 562                                            is a free one.  */
 563 extern unsigned target_pres_cost;       /* The cost for register when there are
 564                                            not too many free ones.  */
 565 extern unsigned target_spill_cost;      /* The cost for register when we need
 566                                            to spill.  */
 567
 568 /* Register pressure estimation for induction variable optimizations & loop
 569    invariant motion.  */
 570 extern unsigned global_cost_for_size (unsigned, unsigned, unsigned);
 571 extern void init_set_costs (void);
 572
 573 /* Loop optimizer initialization.  */
 574 extern void loop_optimizer_init (unsigned);
 575 extern void loop_optimizer_finalize (void);
 576
 577 /* Optimization passes.  */
 578 extern void unswitch_loops (void);
 579
 580 enum
 581 {
 582   UAP_PEEL = 1,         /* Enables loop peeling.  */
 583   UAP_UNROLL = 2,       /* Enables unrolling of loops if it seems profitable.  */
 584   UAP_UNROLL_ALL = 4    /* Enables unrolling of all loops.  */
 585 };
 586
 587 extern void unroll_and_peel_loops (int);
 588 extern void doloop_optimize_loops (void);
 589 extern void move_loop_invariants (void);
 590
 591 #endif /* GCC_CFGLOOP_H */