Re: [PATCH]: Improved handling of COND_EXPR in middle-end passes

[Dorit Nuzman <DORIT at il dot ibm dot com>]

> Hello,
>
...
>
> I just came over another situation in that support for rhs COND_EXPR
> makes things easier:  Some loops may have # of iterations expressed as
> (n <= 0 ? 1 : n).  If we need to use this expression for number of
> iterations (which e.g. vectorizer needs), if COND_EXPR may be used on
> rhs this is no problem.  If this were not allowed, to emit this
> expression to the program, we would need to alter cfg (which may be
> quite cumbersome).  Of course, it might also make semse to allow rhs
> COND_EXPR only in some optimization passes and lower them afterwards.
>

Just to give a bit of background (from an off-list discussion between
Zdenek, DanyB, Robert, and myself) - the need to express a loop bound as
cond_expr comes up, for example, in loops like this:

      void foo (int n)
      {
        int i = 0;

        do
          {
            a[i] = 0;
            i++;
          }
          while (i < n);
      }

in which if n is negative the number of iterations is 1. Since we can't
determine at compile time which is it going to be (n or 1),
'number_of_iterations_in_loop' returns "don't know" and in turn
vectorization fails. Suggested solutions:

(1) Normalize loops to be obviously positive. I.e. do the following
versioning (regardless of vectorization):

      if (n < 0)
      {
        a[i] = 0;
        i++;
      }
      else
      {
         do
           {
             a[i] = 0;
             i++;
           }
           while (i < n);
      }

(2) Leave it for individual optimizations that really need it to apply loop
versioning. For example, in the case of vectorization, teach the vectorizer
to use 'number_of_iterations_exit' instead of
'number_of_iterations_in_loop', and version on 'may_be_zero' if it is not
false. The vectorizer may be able to combine this with the loop versioning
that it may need to do anyhow to resolve aliasing/alignment issues.

(3) Regardless of if/where/when we choose to version - returning a
cond-expr rather than 'don't know' as the number of iterations is the
simplest and most compact solution for vectorizability sake

Modulo-scheduling is another optimization that can benefit from the above
solutions (also an optimization that needs to know that the loop is
countable).

A potential problem with (1) is that it may cause unnecessary code growth;
in addition to the loop-copies it introduces, we also might create
duplicate loop guards (in many cases, we would not be able to determine
that an equivalent loop guard is already present), which makes the code
worse.  On the other hand, (1) also helps things like VRP, since now it
knows that in the loop, n is positive.  It can then use this to narrow
symbolic ranges of calculations based on the iv's.

Therefore, if we go with (1), we'd want to apply it under certain size
constraints (if the amount to copy is less than some threshold, possibly
depending on -s), and also only if we expect to benefit from the
transformation (e.g. the counter is actually used in some calculation).
Also, we may want to consider making the loop guard a part of the loop
structure (record it somewhere so we won't generate duplicate guards).


dorit

> Zdenek