gcc/doc/gccint/analysis-and-representation-of-loops/number-of-iterations-analysis.rst

   1 ..
   2   Copyright 1988-2022 Free Software Foundation, Inc.
   3   This is part of the GCC manual.
   4   For copying conditions, see the copyright.rst file.
   5
   6 .. index:: Number of iterations analysis
   7
   8 .. _number-of-iterations:
   9
  10 Number of iterations analysis
  11 *****************************
  12
  13 Both on GIMPLE and on RTL, there are functions available to determine
  14 the number of iterations of a loop, with a similar interface.  The
  15 number of iterations of a loop in GCC is defined as the number of
  16 executions of the loop latch.  In many cases, it is not possible to
  17 determine the number of iterations unconditionally -- the determined
  18 number is correct only if some assumptions are satisfied.  The analysis
  19 tries to verify these conditions using the information contained in the
  20 program; if it fails, the conditions are returned together with the
  21 result.  The following information and conditions are provided by the
  22 analysis:
  23
  24 * ``assumptions`` : If this condition is false, the rest of
  25   the information is invalid.
  26
  27 * ``noloop_assumptions`` on RTL, ``may_be_zero`` on GIMPLE: If
  28   this condition is true, the loop exits in the first iteration.
  29
  30 * ``infinite`` : If this condition is true, the loop is infinite.
  31   This condition is only available on RTL.  On GIMPLE, conditions for
  32   finiteness of the loop are included in ``assumptions``.
  33
  34 * ``niter_expr`` on RTL, ``niter`` on GIMPLE: The expression
  35   that gives number of iterations.  The number of iterations is defined as
  36   the number of executions of the loop latch.
  37
  38 Both on GIMPLE and on RTL, it necessary for the induction variable
  39 analysis framework to be initialized (SCEV on GIMPLE, loop-iv on RTL).
  40 On GIMPLE, the results are stored to ``struct tree_niter_desc``
  41 structure.  Number of iterations before the loop is exited through a
  42 given exit can be determined using ``number_of_iterations_exit``
  43 function.  On RTL, the results are returned in ``struct niter_desc``
  44 structure.  The corresponding function is named
  45 ``check_simple_exit``.  There are also functions that pass through
  46 all the exits of a loop and try to find one with easy to determine
  47 number of iterations -- ``find_loop_niter`` on GIMPLE and
  48 ``find_simple_exit`` on RTL.  Finally, there are functions that
  49 provide the same information, but additionally cache it, so that
  50 repeated calls to number of iterations are not so costly --
  51 ``number_of_latch_executions`` on GIMPLE and ``get_simple_loop_desc``
  52 on RTL.
  53
  54 Note that some of these functions may behave slightly differently than
  55 others -- some of them return only the expression for the number of
  56 iterations, and fail if there are some assumptions.  The function
  57 ``number_of_latch_executions`` works only for single-exit loops.
  58 The function ``number_of_cond_exit_executions`` can be used to
  59 determine number of executions of the exit condition of a single-exit
  60 loop (i.e., the ``number_of_latch_executions`` increased by one).
  61
  62 On GIMPLE, below constraint flags affect semantics of some APIs of number
  63 of iterations analyzer:
  64
  65 * ``LOOP_C_INFINITE`` : If this constraint flag is set, the loop
  66   is known to be infinite.  APIs like ``number_of_iterations_exit`` can
  67   return false directly without doing any analysis.
  68
  69 * ``LOOP_C_FINITE`` : If this constraint flag is set, the loop is
  70   known to be finite, in other words, loop's number of iterations can be
  71   computed with ``assumptions`` be true.
  72
  73 Generally, the constraint flags are set/cleared by consumers which are
  74 loop optimizers.  It's also the consumers' responsibility to set/clear
  75 constraints correctly.  Failing to do that might result in hard to track
  76 down bugs in scev/niter consumers.  One typical use case is vectorizer:
  77 it drives number of iterations analyzer by setting ``LOOP_C_FINITE``
  78 and vectorizes possibly infinite loop by versioning loop with analysis
  79 result.  In return, constraints set by consumers can also help number of
  80 iterations analyzer in following optimizers.  For example, ``niter``
  81 of a loop versioned under ``assumptions`` is valid unconditionally.
  82
  83 Other constraints may be added in the future, for example, a constraint
  84 indicating that loops' latch must roll thus ``may_be_zero`` would be
  85 false unconditionally.