gcc/cfgloop.h

   1 /* Natural loop functions
   2    Copyright (C) 1987, 1997, 1998, 1999, 2000, 2001, 2002, 2003
   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, 59 Temple Place - Suite 330, Boston, MA
  20 02111-1307, USA.  */
  21
  22 /* Structure to hold decision about unrolling/peeling.  */
  23 enum lpt_dec
  24 {
  25   LPT_NONE,
  26   LPT_PEEL_COMPLETELY,
  27   LPT_PEEL_SIMPLE,
  28   LPT_UNROLL_CONSTANT,
  29   LPT_UNROLL_RUNTIME,
  30   LPT_UNROLL_STUPID
  31 };
  32
  33 struct lpt_decision
  34 {
  35   enum lpt_dec decision;
  36   unsigned times;
  37 };
  38
  39 /* Description of loop for simple loop unrolling.  */
  40 struct loop_desc
  41 {
  42   int postincr;         /* 1 if increment/decrement is done after loop exit condition.  */
  43   rtx stride;           /* Value added to VAR in each iteration.  */
  44   rtx var;              /* Loop control variable.  */
  45   rtx var_alts;         /* List of definitions of its initial value.  */
  46   rtx lim;              /* Expression var is compared with.  */
  47   rtx lim_alts;         /* List of definitions of its initial value.  */
  48   bool const_iter;      /* True if it iterates constant number of times.  */
  49   unsigned HOST_WIDE_INT niter;
  50                         /* Number of iterations if it is constant.  */
  51   bool may_be_zero;     /* If we cannot determine that the first iteration will pass.  */
  52   enum rtx_code cond;   /* Exit condition.  */
  53   int neg;              /* Set to 1 if loop ends when condition is satisfied.  */
  54   edge out_edge;        /* The exit edge.  */
  55   edge in_edge;         /* And the other one.  */
  56   int n_branches;       /* Number of branches inside the loop.  */
  57 };
  58
  59 /* Structure to hold information for each natural loop.  */
  60 struct loop
  61 {
  62   /* Index into loops array.  */
  63   int num;
  64
  65   /* Basic block of loop header.  */
  66   basic_block header;
  67
  68   /* Basic block of loop latch.  */
  69   basic_block latch;
  70
  71   /* Basic block of loop preheader or NULL if it does not exist.  */
  72   basic_block pre_header;
  73
  74   /* For loop unrolling/peeling decision.  */
  75   struct lpt_decision lpt_decision;
  76
  77   /* Simple loop description.  */
  78   int simple;
  79   struct loop_desc desc;
  80   int has_desc;
  81
  82   /* Number of loop insns.  */
  83   unsigned ninsns;
  84
  85   /* Average number of executed insns per iteration.  */
  86   unsigned av_ninsns;
  87
  88   /* Array of edges along the preheader extended basic block trace.
  89      The source of the first edge is the root node of preheader
  90      extended basic block, if it exists.  */
  91   edge *pre_header_edges;
  92
  93   /* Number of edges along the pre_header extended basic block trace.  */
  94   int num_pre_header_edges;
  95
  96   /* The first block in the loop.  This is not necessarily the same as
  97      the loop header.  */
  98   basic_block first;
  99
 100   /* The last block in the loop.  This is not necessarily the same as
 101      the loop latch.  */
 102   basic_block last;
 103
 104   /* Bitmap of blocks contained within the loop.  */
 105   sbitmap nodes;
 106
 107   /* Number of blocks contained within the loop.  */
 108   unsigned num_nodes;
 109
 110   /* Array of edges that enter the loop.  */
 111   edge *entry_edges;
 112
 113   /* Number of edges that enter the loop.  */
 114   int num_entries;
 115
 116   /* Array of edges that exit the loop.  */
 117   edge *exit_edges;
 118
 119   /* Number of edges that exit the loop.  */
 120   int num_exits;
 121
 122   /* Bitmap of blocks that dominate all exits of the loop.  */
 123   sbitmap exits_doms;
 124
 125   /* The loop nesting depth.  */
 126   int depth;
 127
 128   /* Superloops of the loop.  */
 129   struct loop **pred;
 130
 131   /* The height of the loop (enclosed loop levels) within the loop
 132      hierarchy tree.  */
 133   int level;
 134
 135   /* The outer (parent) loop or NULL if outermost loop.  */
 136   struct loop *outer;
 137
 138   /* The first inner (child) loop or NULL if innermost loop.  */
 139   struct loop *inner;
 140
 141   /* Link to the next (sibling) loop.  */
 142   struct loop *next;
 143
 144   /* Loop that is copy of this loop.  */
 145   struct loop *copy;
 146
 147   /* Non-zero if the loop is invalid (e.g., contains setjmp.).  */
 148   int invalid;
 149
 150   /* Auxiliary info specific to a pass.  */
 151   void *aux;
 152
 153   /* The following are currently used by loop.c but they are likely to
 154      disappear as loop.c is converted to use the CFG.  */
 155
 156   /* Non-zero if the loop has a NOTE_INSN_LOOP_VTOP.  */
 157   rtx vtop;
 158
 159   /* Non-zero if the loop has a NOTE_INSN_LOOP_CONT.
 160      A continue statement will generate a branch to NEXT_INSN (cont).  */
 161   rtx cont;
 162
 163   /* The dominator of cont.  */
 164   rtx cont_dominator;
 165
 166   /* The NOTE_INSN_LOOP_BEG.  */
 167   rtx start;
 168
 169   /* The NOTE_INSN_LOOP_END.  */
 170   rtx end;
 171
 172   /* For a rotated loop that is entered near the bottom,
 173      this is the label at the top.  Otherwise it is zero.  */
 174   rtx top;
 175
 176   /* Place in the loop where control enters.  */
 177   rtx scan_start;
 178
 179   /* The position where to sink insns out of the loop.  */
 180   rtx sink;
 181
 182   /* List of all LABEL_REFs which refer to code labels outside the
 183      loop.  Used by routines that need to know all loop exits, such as
 184      final_biv_value and final_giv_value.
 185
 186      This does not include loop exits due to return instructions.
 187      This is because all bivs and givs are pseudos, and hence must be
 188      dead after a return, so the presence of a return does not affect
 189      any of the optimizations that use this info.  It is simpler to
 190      just not include return instructions on this list.  */
 191   rtx exit_labels;
 192
 193   /* The number of LABEL_REFs on exit_labels for this loop and all
 194      loops nested inside it.  */
 195   int exit_count;
 196 };
 197
 198 /* Flags for state of loop structure.  */
 199 enum
 200 {
 201   LOOPS_HAVE_PREHEADERS = 1,
 202   LOOPS_HAVE_SIMPLE_LATCHES = 2,
 203   LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS = 4
 204 };
 205
 206 /* Structure to hold CFG information about natural loops within a function.  */
 207 struct loops
 208 {
 209   /* Number of natural loops in the function.  */
 210   unsigned num;
 211
 212   /* Maximum nested loop level in the function.  */
 213   unsigned levels;
 214
 215   /* Array of natural loop descriptors (scanning this array in reverse order
 216      will find the inner loops before their enclosing outer loops).  */
 217   struct loop *array;
 218
 219   /* The above array is unused in new loop infrastructure and is kept only for
 220      purposes of the old loop optimizer.  Instead we store just pointers to
 221      loops here.  */
 222   struct loop **parray;
 223
 224   /* Pointer to root of loop hierarchy tree.  */
 225   struct loop *tree_root;
 226
 227   /* Information derived from the CFG.  */
 228   struct cfg
 229   {
 230     /* The bitmap vector of dominators or NULL if not computed.  */
 231     dominance_info dom;
 232
 233     /* The ordering of the basic blocks in a depth first search.  */
 234     int *dfs_order;
 235
 236     /* The reverse completion ordering of the basic blocks found in a
 237        depth first search.  */
 238     int *rc_order;
 239   } cfg;
 240
 241   /* Headers shared by multiple loops that should be merged.  */
 242   sbitmap shared_headers;
 243
 244   /* State of loops.  */
 245   int state;
 246 };
 247
 248 /* Flags for loop discovery.  */
 249
 250 #define LOOP_TREE               1       /* Build loop hierarchy tree.  */
 251 #define LOOP_PRE_HEADER         2       /* Analyze loop preheader.  */
 252 #define LOOP_ENTRY_EDGES        4       /* Find entry edges.  */
 253 #define LOOP_EXIT_EDGES         8       /* Find exit edges.  */
 254 #define LOOP_EDGES              (LOOP_ENTRY_EDGES | LOOP_EXIT_EDGES)
 255 #define LOOP_ALL               15       /* All of the above  */
 256
 257 /* Loop recognition.  */
 258 extern int flow_loops_find              PARAMS ((struct loops *, int flags));
 259 extern int flow_loops_update            PARAMS ((struct loops *, int flags));
 260 extern void flow_loops_free             PARAMS ((struct loops *));
 261 extern void flow_loops_dump             PARAMS ((const struct loops *, FILE *,
 262                                                 void (*)(const struct loop *,
 263                                                 FILE *, int), int));
 264 extern void flow_loop_dump              PARAMS ((const struct loop *, FILE *,
 265                                                 void (*)(const struct loop *,
 266                                                 FILE *, int), int));
 267 extern int flow_loop_scan               PARAMS ((struct loops *,
 268                                                 struct loop *, int));
 269 extern void flow_loop_free              PARAMS ((struct loop *));
 270 void mark_irreducible_loops             PARAMS ((struct loops *));
 271
 272 /* Loop datastructure manipulation/querying.  */
 273 extern void flow_loop_tree_node_add     PARAMS ((struct loop *, struct loop *));
 274 extern void flow_loop_tree_node_remove  PARAMS ((struct loop *));
 275 extern bool flow_loop_outside_edge_p    PARAMS ((const struct loop *, edge));
 276 extern bool flow_loop_nested_p          PARAMS ((const struct loop *,
 277                                                 const struct loop *));
 278 extern bool flow_bb_inside_loop_p       PARAMS ((const struct loop *,
 279                                                 const basic_block));
 280 extern struct loop * find_common_loop   PARAMS ((struct loop *, struct loop *));
 281 extern int num_loop_insns               PARAMS ((struct loop *));
 282 extern int average_num_loop_insns       PARAMS ((struct loop *));
 283
 284 /* Loops & cfg manipulation.  */
 285 extern basic_block *get_loop_body       PARAMS ((const struct loop *));
 286 extern edge *get_loop_exit_edges        PARAMS ((const struct loop *, unsigned *));
 287
 288 extern edge loop_preheader_edge         PARAMS ((const struct loop *));
 289 extern edge loop_latch_edge             PARAMS ((const struct loop *));
 290
 291 extern void add_bb_to_loop              PARAMS ((basic_block, struct loop *));
 292 extern void remove_bb_from_loops        PARAMS ((basic_block));
 293
 294 extern void cancel_loop                 PARAMS ((struct loops *, struct loop *));
 295 extern void cancel_loop_tree            PARAMS ((struct loops *, struct loop *));
 296
 297 extern basic_block loop_split_edge_with PARAMS ((edge, rtx, struct loops *));
 298 extern int fix_loop_placement           PARAMS ((struct loop *));
 299
 300 enum
 301 {
 302   CP_SIMPLE_PREHEADERS = 1,
 303   CP_INSIDE_CFGLAYOUT = 2
 304 };
 305
 306 extern void create_preheaders           PARAMS ((struct loops *, int));
 307 extern void force_single_succ_latches   PARAMS ((struct loops *));
 308
 309 extern void verify_loop_structure       PARAMS ((struct loops *));
 310
 311 /* Loop analysis.  */
 312 extern bool simple_loop_p               PARAMS ((struct loops *, struct loop *,
 313                                                 struct loop_desc *));
 314 extern rtx count_loop_iterations        PARAMS ((struct loop_desc *, rtx, rtx));
 315 extern bool just_once_each_iteration_p  PARAMS ((struct loops *,struct loop *,
 316                                                  basic_block));
 317 extern unsigned expected_loop_iterations PARAMS ((const struct loop *));
 318
 319 /* Loop manipulation.  */
 320 extern bool can_duplicate_loop_p        PARAMS ((struct loop *loop));
 321
 322 #define DLTHE_FLAG_UPDATE_FREQ  1       /* Update frequencies in
 323                                            duplicate_loop_to_header_edge.  */
 324
 325 extern int duplicate_loop_to_header_edge PARAMS ((struct loop *, edge,
 326                                                 struct loops *, unsigned,
 327                                                 sbitmap, edge, edge *,
 328                                                 unsigned *, int));
 329 extern struct loop *loopify             PARAMS ((struct loops *, edge,
 330                                                 edge, basic_block));
 331 extern void unloop                      PARAMS ((struct loops *, struct loop *));
 332 extern bool remove_path                 PARAMS ((struct loops *, edge));
 333 extern edge split_loop_bb               PARAMS ((struct loops *, basic_block,
 334                                                 rtx));
 335
 336 /* Loop optimizer initialization.  */
 337 extern struct loops *loop_optimizer_init PARAMS ((FILE *));
 338 extern void loop_optimizer_finalize     PARAMS ((struct loops *, FILE *));
 339
 340 /* Optimization passes.  */
 341 extern void unswitch_loops              PARAMS ((struct loops *));
 342
 343 enum
 344 {
 345   UAP_PEEL = 1,         /* Enables loop peeling.  */
 346   UAP_UNROLL = 2,       /* Enables peeling of loops if it seems profitable.  */
 347   UAP_UNROLL_ALL = 4    /* Enables peeling of all loops.  */
 348 };
 349
 350 extern void unroll_and_peel_loops       PARAMS ((struct loops *, int));