Elim anonymous range construction

When iterating over a range such as:
  for i in 1..10 do ...

we end up constructing a range and then getting it's low and high values out.
The range creation adds additional overhead that is not needed and it
obfuscates the loop from the backend compiler (it probably can't figure out the
number of iterations even though the chapel compiler knowns it at compile
time.)

Ideally we want to generate
  for i in 1..10
as
  for(i=1; i<=10; i+=1)

This removes the construction cost, and should allow the backend compiler to
optimize/auto-vectorize better.

To accomplish this, this replaces anonymous ranges with direct iterator calls
in for/coforall loops. Ranges are iterable because they have a these() method.
This replaces the chpl_build_bounded_range with a direct call to an iterator. It
essentially replaces the code:
  for i in 1..10
with:
  for i in chpl_direct_range_iter(1, 10, 1)

the end result is that
  for i in 1..10
is now generated as:
  int64_t i;
  for (i = INT64(1); (i <= INT64(10)); i += INT64(1)) {}

which is exactly what we wanted

This also handles anonymous ranges whose stride is known at compile time, as
well as zippered iterators and iterators over non literals:

e.g.
  var lo=1, hi=10;
  for (i, j) in zip(lo..hi by 2, 1..10 by -2)
generates (with shortened names):
  for (val = lo, val2 = INT64(10); (val <= hi); val += INT64(2), val2 += INT64(-2))

Note that this does nothing for aligned ranges, and doesn't handle cases such as
for i in 1..10 by 2 by 2 since it doesn't seem like a common case. It also
doesn't handle the # operator or unbounded ranges.

The first attempt to do this was to replace the entire for loop with a c for
loop directly, but you can't do that for zippered iterators and figuring out
the type of the stride is really difficult and you have to insert calls to the
overflow checking and the general iterator.

A better long term solution might be to expand scalarReplacementOfAggregates to
includes ranges. That would allow all ranges to be optimized, including
non-anonymous ranges, and ranges that are used in contexts other than direct
iteration.


Some implementation details:
 - The code to call a direct range iterator is pretty heavily commented so this
   is just a brief overview

 - while building for/coforall loops we look for iteratorExpr's of the form
   "low..high" and "low..high by stride". If we find one we replace the
   build_range with a call to chpl_direct_range_iter(low, high stride). This
   chpl_direct_range_iter is implemented in ChapelRange. There are several versions
   of the iterator to handle the different index and stride types. These
   iterators are just wrappers to handle the index and stride types and
   argument coercion and they call down to the real iterators that directly use
   C for loops. The iterators take care to preserve semantics and warnings that
   range construction has such as warning about a stride of 0, stride to large
   for the idxType, and incompatible index types. They also do overflow
   checking and will use the general iterator if useOptimizedRangIterators is
   false.

 - In order to support bounds checking, the checkIfIterWillOverflow was updated
   to take all the parts of the range it checked as arguments so that the
   direct range iterator could call it.

 - I also removed the 'by' procs that took the step as a param because they
   stamped out a new function for all ranges that had a param stride, with no
   real benefit

This has a really nice impact on the generated code, but unfortunately I didn't
see any real performance impact at least with nbody.


On Dec 18, 2014, at 8:03 AM, Brad Chamberlain <notifications@github.com<mailto:notifications@github.com>> wrote:


In compiler/AST/ForLoop.cpp<https://github.com/chapel-lang/chapel/pull/1021#discussion-diff-22050601>:

> +      Expr* high = range->get(2)->copy();
> +      iteratorExpr = new CallExpr("chpl_direct_range_iter", low, high, stride);
> +    }
> +  }
> +  return iteratorExpr;
> +}
> +
> +static Expr* optimizeAnonymousRangeIteration(Expr* iteratorExpr, bool zippered)
> +{
> +  iteratorExpr = tryToUseDirectRangeIterator(iteratorExpr);
> +  // for zippered iterators, try to replace each iterator of the tuple
> +  if (zippered)
> +    if (CallExpr* call = toCallExpr(iteratorExpr))
> +      if (call->isNamed("_build_tuple"))
> +        for_actuals(actual, call)
> +          actual->replace(tryToUseDirectRangeIterator(actual->copy()));


I'm neither defending nor attacking the current scheme -- I'm reasonably neutral, primarily due to ignorance. I'm just trying to ascertain that nobody's proposing that, as part of this patch, Elliot should also rewrite the AST GC scheme; and if that's true, I'm trying to ascertain what he should do beyond what he's got here (if anything). I'm not convinced anything more is necessary, but don't understand the GC as well as you guys may.

—
Reply to this email directly or view it on GitHub<https://github.com/chapel-lang/chapel/pull/1021/files#r22050601>.

You can be confident that I am not proposing reworking AST memory management
as part of this PR.  It is easy to imagine that the day will come when we want to revisit
it but I don’t have any time frame in mind.  I was simply trying to clarify that (a) we don’t
currently have a mark/sweep collector (b) that it would be “easy” to break the current
scheme if one programs without any awareness of the assumptions it makes.

Mike