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 #include "double-int.h"
  30
  31 /* Structure to hold decision about unrolling/peeling.  */
  32 enum lpt_dec
  33 {
  34   LPT_NONE,
  35   LPT_PEEL_COMPLETELY,
  36   LPT_PEEL_SIMPLE,
  37   LPT_UNROLL_CONSTANT,
  38   LPT_UNROLL_RUNTIME,
  39   LPT_UNROLL_STUPID
  40 };
  41
  42 struct lpt_decision GTY (())
  43 {
  44   enum lpt_dec decision;
  45   unsigned times;
  46 };
  47
  48 /* The structure describing a bound on number of iterations of a loop.  */
  49
  50 struct nb_iter_bound GTY ((chain_next ("%h.next")))
  51 {
  52   /* The statement STMT is executed at most ...  */
  53   tree stmt;
  54
  55   /* ... BOUND + 1 times (BOUND must be an unsigned constant).
  56      The + 1 is added for the following reasons:
  57
  58      a) 0 would otherwise be unused, while we would need to care more about
  59         overflows (as MAX + 1 is sometimes produced as the estimate on number
  60         of executions of STMT).
  61      b) it is consistent with the result of number_of_iterations_exit.  */
  62   double_int bound;
  63
  64   /* True if the statement will cause the loop to be leaved the (at most)
  65      BOUND + 1-st time it is executed, that is, all the statements after it
  66      are executed at most BOUND times.  */
  67   bool is_exit;
  68
  69   /* The next bound in the list.  */
  70   struct nb_iter_bound *next;
  71 };
  72
  73 /* Description of the loop exit.  */
  74
  75 struct loop_exit GTY (())
  76 {
  77   /* The exit edge.  */
  78   struct edge_def *e;
  79
  80   /* Previous and next exit in the list of the exits of the loop.  */
  81   struct loop_exit *prev;
  82   struct loop_exit *next;
  83
  84   /* Next element in the list of loops from that E exits.  */
  85   struct loop_exit *next_e;
  86 };
  87
  88 typedef struct loop *loop_p;
  89 DEF_VEC_P (loop_p);
  90 DEF_VEC_ALLOC_P (loop_p, heap);
  91 DEF_VEC_ALLOC_P (loop_p, gc);
  92
  93 /* Structure to hold information for each natural loop.  */
  94 struct loop GTY ((chain_next ("%h.next")))
  95 {
  96   /* Index into loops array.  */
  97   int num;
  98
  99   /* Basic block of loop header.  */
 100   struct basic_block_def *header;
 101
 102   /* Basic block of loop latch.  */
 103   struct basic_block_def *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   /* Superloops of the loop, starting with the outermost loop.  */
 118   VEC (loop_p, gc) *superloops;
 119
 120   /* The first inner (child) loop or NULL if innermost loop.  */
 121   struct loop *inner;
 122
 123   /* Link to the next (sibling) loop.  */
 124   struct loop *next;
 125
 126   /* Auxiliary info specific to a pass.  */
 127   PTR GTY ((skip (""))) aux;
 128
 129   /* The number of times the latch of the loop is executed.
 130      This is an INTEGER_CST or an expression containing symbolic
 131      names.  Don't access this field directly:
 132      number_of_latch_executions computes and caches the computed
 133      information in this field.  */
 134   tree nb_iterations;
 135
 136   /* An integer estimation of the number of iterations.  Estimate_state
 137      describes what is the state of the estimation.  */
 138   enum
 139     {
 140       /* Estimate was not computed yet.  */
 141       EST_NOT_COMPUTED,
 142       /* Estimate is ready.  */
 143       EST_AVAILABLE
 144     } estimate_state;
 145
 146   /* An integer guaranteed to bound the number of iterations of the loop
 147      from above.  */
 148   bool any_upper_bound;
 149   double_int nb_iterations_upper_bound;
 150
 151   /* An integer giving the expected number of iterations of the loop.  */
 152   bool any_estimate;
 153   double_int nb_iterations_estimate;
 154
 155   /* Upper bound on number of iterations of a loop.  */
 156   struct nb_iter_bound *bounds;
 157
 158   /* Head of the cyclic list of the exits of the loop.  */
 159   struct loop_exit *exits;
 160 };
 161
 162 /* Flags for state of loop structure.  */
 163 enum
 164 {
 165   LOOPS_HAVE_PREHEADERS = 1,
 166   LOOPS_HAVE_SIMPLE_LATCHES = 2,
 167   LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS = 4,
 168   LOOPS_HAVE_RECORDED_EXITS = 8,
 169   LOOPS_MAY_HAVE_MULTIPLE_LATCHES = 16,
 170   LOOP_CLOSED_SSA = 32
 171 };
 172
 173 #define LOOPS_NORMAL (LOOPS_HAVE_PREHEADERS | LOOPS_HAVE_SIMPLE_LATCHES \
 174                       | LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)
 175 #define AVOID_CFG_MODIFICATIONS (LOOPS_MAY_HAVE_MULTIPLE_LATCHES)
 176
 177 /* Structure to hold CFG information about natural loops within a function.  */
 178 struct loops GTY (())
 179 {
 180   /* State of loops.  */
 181   int state;
 182
 183   /* Array of the loops.  */
 184   VEC (loop_p, gc) *larray;
 185
 186   /* Maps edges to the list of their descriptions as loop exits.  Edges
 187      whose sources or destinations have loop_father == NULL (which may
 188      happen during the cfg manipulations) should not appear in EXITS.  */
 189   htab_t GTY((param_is (struct loop_exit))) exits;
 190
 191   /* Pointer to root of loop hierarchy tree.  */
 192   struct loop *tree_root;
 193 };
 194
 195 /* Loop recognition.  */
 196 extern int flow_loops_find (struct loops *);
 197 extern void disambiguate_loops_with_multiple_latches (void);
 198 extern void flow_loops_free (struct loops *);
 199 extern void flow_loops_dump (FILE *,
 200                              void (*)(const struct loop *, FILE *, int), int);
 201 extern void flow_loop_dump (const struct loop *, FILE *,
 202                             void (*)(const struct loop *, FILE *, int), int);
 203 struct loop *alloc_loop (void);
 204 extern void flow_loop_free (struct loop *);
 205 int flow_loop_nodes_find (basic_block, struct loop *);
 206 void fix_loop_structure (bitmap changed_bbs);
 207 void mark_irreducible_loops (void);
 208 void release_recorded_exits (void);
 209 void record_loop_exits (void);
 210 void rescan_loop_exit (edge, bool, bool);
 211
 212 /* Loop data structure manipulation/querying.  */
 213 extern void flow_loop_tree_node_add (struct loop *, struct loop *);
 214 extern void flow_loop_tree_node_remove (struct loop *);
 215 extern void add_loop (struct loop *, struct loop *);
 216 extern bool flow_loop_nested_p  (const struct loop *, const struct loop *);
 217 extern bool flow_bb_inside_loop_p (const struct loop *, const basic_block);
 218 extern struct loop * find_common_loop (struct loop *, struct loop *);
 219 struct loop *superloop_at_depth (struct loop *, unsigned);
 220 struct eni_weights_d;
 221 extern unsigned tree_num_loop_insns (struct loop *, struct eni_weights_d *);
 222 extern int num_loop_insns (struct loop *);
 223 extern int average_num_loop_insns (struct loop *);
 224 extern unsigned get_loop_level (const struct loop *);
 225 extern bool loop_exit_edge_p (const struct loop *, edge);
 226 extern void mark_loop_exit_edges (void);
 227
 228 /* Loops & cfg manipulation.  */
 229 extern basic_block *get_loop_body (const struct loop *);
 230 extern unsigned get_loop_body_with_size (const struct loop *, basic_block *,
 231                                          unsigned);
 232 extern basic_block *get_loop_body_in_dom_order (const struct loop *);
 233 extern basic_block *get_loop_body_in_bfs_order (const struct loop *);
 234 extern VEC (edge, heap) *get_loop_exit_edges (const struct loop *);
 235 edge single_exit (const struct loop *);
 236 extern unsigned num_loop_branches (const struct loop *);
 237
 238 extern edge loop_preheader_edge (const struct loop *);
 239 extern edge loop_latch_edge (const struct loop *);
 240
 241 extern void add_bb_to_loop (basic_block, struct loop *);
 242 extern void remove_bb_from_loops (basic_block);
 243
 244 extern void cancel_loop_tree (struct loop *);
 245 extern void delete_loop (struct loop *);
 246
 247 enum
 248 {
 249   CP_SIMPLE_PREHEADERS = 1
 250 };
 251
 252 basic_block create_preheader (struct loop *, int);
 253 extern void create_preheaders (int);
 254 extern void force_single_succ_latches (void);
 255
 256 extern void verify_loop_structure (void);
 257
 258 /* Loop analysis.  */
 259 extern bool just_once_each_iteration_p (const struct loop *, basic_block);
 260 gcov_type expected_loop_iterations_unbounded (const struct loop *);
 261 extern unsigned expected_loop_iterations (const struct loop *);
 262 extern rtx doloop_condition_get (rtx);
 263
 264 void estimate_numbers_of_iterations_loop (struct loop *);
 265 HOST_WIDE_INT estimated_loop_iterations_int (struct loop *, bool);
 266 bool estimated_loop_iterations (struct loop *, bool, double_int *);
 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 number of superloops of LOOP.  */
 407
 408 static inline unsigned
 409 loop_depth (const struct loop *loop)
 410 {
 411   return VEC_length (loop_p, loop->superloops);
 412 }
 413
 414 /* Returns the immediate superloop of LOOP, or NULL if LOOP is the outermost
 415    loop.  */
 416
 417 static inline struct loop *
 418 loop_outer (const struct loop *loop)
 419 {
 420   unsigned n = VEC_length (loop_p, loop->superloops);
 421
 422   if (n == 0)
 423     return NULL;
 424
 425   return VEC_index (loop_p, loop->superloops, n - 1);
 426 }
 427
 428 /* Returns the list of loops in current_loops.  */
 429
 430 static inline VEC (loop_p, gc) *
 431 get_loops (void)
 432 {
 433   if (!current_loops)
 434     return NULL;
 435
 436   return current_loops->larray;
 437 }
 438
 439 /* Returns the number of loops in current_loops (including the removed
 440    ones and the fake loop that forms the root of the loop tree).  */
 441
 442 static inline unsigned
 443 number_of_loops (void)
 444 {
 445   if (!current_loops)
 446     return 0;
 447
 448   return VEC_length (loop_p, current_loops->larray);
 449 }
 450
 451 /* Loop iterators.  */
 452
 453 /* Flags for loop iteration.  */
 454
 455 enum li_flags
 456 {
 457   LI_INCLUDE_ROOT = 1,          /* Include the fake root of the loop tree.  */
 458   LI_FROM_INNERMOST = 2,        /* Iterate over the loops in the reverse order,
 459                                    starting from innermost ones.  */
 460   LI_ONLY_INNERMOST = 4         /* Iterate only over innermost loops.  */
 461 };
 462
 463 /* The iterator for loops.  */
 464
 465 typedef struct
 466 {
 467   /* The list of loops to visit.  */
 468   VEC(int,heap) *to_visit;
 469
 470   /* The index of the actual loop.  */
 471   unsigned idx;
 472 } loop_iterator;
 473
 474 static inline void
 475 fel_next (loop_iterator *li, loop_p *loop)
 476 {
 477   int anum;
 478
 479   while (VEC_iterate (int, li->to_visit, li->idx, anum))
 480     {
 481       li->idx++;
 482       *loop = get_loop (anum);
 483       if (*loop)
 484         return;
 485     }
 486
 487   VEC_free (int, heap, li->to_visit);
 488   *loop = NULL;
 489 }
 490
 491 static inline void
 492 fel_init (loop_iterator *li, loop_p *loop, unsigned flags)
 493 {
 494   struct loop *aloop;
 495   unsigned i;
 496   int mn;
 497
 498   li->idx = 0;
 499   if (!current_loops)
 500     {
 501       li->to_visit = NULL;
 502       *loop = NULL;
 503       return;
 504     }
 505
 506   li->to_visit = VEC_alloc (int, heap, number_of_loops ());
 507   mn = (flags & LI_INCLUDE_ROOT) ? 0 : 1;
 508
 509   if (flags & LI_ONLY_INNERMOST)
 510     {
 511       for (i = 0; VEC_iterate (loop_p, current_loops->larray, i, aloop); i++)
 512         if (aloop != NULL
 513             && aloop->inner == NULL
 514             && aloop->num >= mn)
 515           VEC_quick_push (int, li->to_visit, aloop->num);
 516     }
 517   else if (flags & LI_FROM_INNERMOST)
 518     {
 519       /* Push the loops to LI->TO_VISIT in postorder.  */
 520       for (aloop = current_loops->tree_root;
 521            aloop->inner != NULL;
 522            aloop = aloop->inner)
 523         continue;
 524
 525       while (1)
 526         {
 527           if (aloop->num >= mn)
 528             VEC_quick_push (int, li->to_visit, aloop->num);
 529
 530           if (aloop->next)
 531             {
 532               for (aloop = aloop->next;
 533                    aloop->inner != NULL;
 534                    aloop = aloop->inner)
 535                 continue;
 536             }
 537           else if (!loop_outer (aloop))
 538             break;
 539           else
 540             aloop = loop_outer (aloop);
 541         }
 542     }
 543   else
 544     {
 545       /* Push the loops to LI->TO_VISIT in preorder.  */
 546       aloop = current_loops->tree_root;
 547       while (1)
 548         {
 549           if (aloop->num >= mn)
 550             VEC_quick_push (int, li->to_visit, aloop->num);
 551
 552           if (aloop->inner != NULL)
 553             aloop = aloop->inner;
 554           else
 555             {
 556               while (aloop != NULL && aloop->next == NULL)
 557                 aloop = loop_outer (aloop);
 558               if (aloop == NULL)
 559                 break;
 560               aloop = aloop->next;
 561             }
 562         }
 563     }
 564
 565   fel_next (li, loop);
 566 }
 567
 568 #define FOR_EACH_LOOP(LI, LOOP, FLAGS) \
 569   for (fel_init (&(LI), &(LOOP), FLAGS); \
 570        (LOOP); \
 571        fel_next (&(LI), &(LOOP)))
 572
 573 #define FOR_EACH_LOOP_BREAK(LI) \
 574   { \
 575     VEC_free (int, heap, (LI)->to_visit); \
 576     break; \
 577   }
 578
 579 /* The properties of the target.  */
 580
 581 extern unsigned target_avail_regs;
 582 extern unsigned target_res_regs;
 583 extern unsigned target_reg_cost;
 584 extern unsigned target_spill_cost;
 585
 586 /* Register pressure estimation for induction variable optimizations & loop
 587    invariant motion.  */
 588 extern unsigned estimate_reg_pressure_cost (unsigned, unsigned);
 589 extern void init_set_costs (void);
 590
 591 /* Loop optimizer initialization.  */
 592 extern void loop_optimizer_init (unsigned);
 593 extern void loop_optimizer_finalize (void);
 594
 595 /* Optimization passes.  */
 596 extern void unswitch_loops (void);
 597
 598 enum
 599 {
 600   UAP_PEEL = 1,         /* Enables loop peeling.  */
 601   UAP_UNROLL = 2,       /* Enables unrolling of loops if it seems profitable.  */
 602   UAP_UNROLL_ALL = 4    /* Enables unrolling of all loops.  */
 603 };
 604
 605 extern void unroll_and_peel_loops (int);
 606 extern void doloop_optimize_loops (void);
 607 extern void move_loop_invariants (void);
 608
 609 #endif /* GCC_CFGLOOP_H */