gccint: Number of iterations
1
1 16.7 Number of iterations analysis
1 ==================================
1
1 Both on GIMPLE and on RTL, there are functions available to determine
1 the number of iterations of a loop, with a similar interface. The
1 number of iterations of a loop in GCC is defined as the number of
1 executions of the loop latch. In many cases, it is not possible to
1 determine the number of iterations unconditionally - the determined
1 number is correct only if some assumptions are satisfied. The analysis
1 tries to verify these conditions using the information contained in the
1 program; if it fails, the conditions are returned together with the
1 result. The following information and conditions are provided by the
1 analysis:
1
1 * 'assumptions': If this condition is false, the rest of the
1 information is invalid.
1 * 'noloop_assumptions' on RTL, 'may_be_zero' on GIMPLE: If this
1 condition is true, the loop exits in the first iteration.
1 * 'infinite': If this condition is true, the loop is infinite. This
1 condition is only available on RTL. On GIMPLE, conditions for
1 finiteness of the loop are included in 'assumptions'.
1 * 'niter_expr' on RTL, 'niter' on GIMPLE: The expression that gives
1 number of iterations. The number of iterations is defined as the
1 number of executions of the loop latch.
1
1 Both on GIMPLE and on RTL, it necessary for the induction variable
1 analysis framework to be initialized (SCEV on GIMPLE, loop-iv on RTL).
1 On GIMPLE, the results are stored to 'struct tree_niter_desc' structure.
1 Number of iterations before the loop is exited through a given exit can
1 be determined using 'number_of_iterations_exit' function. On RTL, the
1 results are returned in 'struct niter_desc' structure. The
1 corresponding function is named 'check_simple_exit'. There are also
1 functions that pass through all the exits of a loop and try to find one
1 with easy to determine number of iterations - 'find_loop_niter' on
1 GIMPLE and 'find_simple_exit' on RTL. Finally, there are functions that
1 provide the same information, but additionally cache it, so that
1 repeated calls to number of iterations are not so costly -
1 'number_of_latch_executions' on GIMPLE and 'get_simple_loop_desc' on
1 RTL.
1
1 Note that some of these functions may behave slightly differently than
1 others - some of them return only the expression for the number of
1 iterations, and fail if there are some assumptions. The function
1 'number_of_latch_executions' works only for single-exit loops. The
1 function 'number_of_cond_exit_executions' can be used to determine
1 number of executions of the exit condition of a single-exit loop (i.e.,
1 the 'number_of_latch_executions' increased by one).
1
1 On GIMPLE, below constraint flags affect semantics of some APIs of
1 number of iterations analyzer:
1
1 * 'LOOP_C_INFINITE': If this constraint flag is set, the loop is
1 known to be infinite. APIs like 'number_of_iterations_exit' can
1 return false directly without doing any analysis.
1 * 'LOOP_C_FINITE': If this constraint flag is set, the loop is known
1 to be finite, in other words, loop's number of iterations can be
1 computed with 'assumptions' be true.
1
1 Generally, the constraint flags are set/cleared by consumers which are
1 loop optimizers. It's also the consumers' responsibility to set/clear
1 constraints correctly. Failing to do that might result in hard to track
1 down bugs in scev/niter consumers. One typical use case is vectorizer:
1 it drives number of iterations analyzer by setting 'LOOP_C_FINITE' and
1 vectorizes possibly infinite loop by versioning loop with analysis
1 result. In return, constraints set by consumers can also help number of
1 iterations analyzer in following optimizers. For example, 'niter' of a
1 loop versioned under 'assumptions' is valid unconditionally.
1
1 Other constraints may be added in the future, for example, a constraint
1 indicating that loops' latch must roll thus 'may_be_zero' would be false
1 unconditionally.
1