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 17, 2014, at 5:10 PM, 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-22018188>:

> +      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()));


[Mike -- got both your mails, but only read the first because I didn't want
to figure out what the diff for the second was]

You guys are definitely way beyond my level of expertise. It sounds like
the issues we're discussing are larger than Elliot's commit (which is
not to say they're not worthwhile, just that I don't know that Elliot should
hold off his commit due to them). If setting parentExpr of the soon-to-be-
orphaned AST node would help it be reclaimed, it sounds like we should
perhaps do that to be good citizens (though presumably there are many
other similar cases that would have similar problems). If there are no
reasons we couldn't do a reaching garbage collector (assuming we aren't),
that seems like the better long-term approach (in that I'd rather be able
to drop things on the floor than have to set certain things to certain states
in order to have it be reclaimed).

—
Reply to this email directly or view it on GitHub<https://github.com/chapel-lang/chapel/pull/1021/files#r22018188>.


I am not a big fan of the current strategy as reflected cleanAst().  It’s hard to debug if
anything goes wrong esp. if you’re dumb enough to try to print the contents of ASTs
in the middle of the process when  parent to child  pointers may be inconsistent.

I think it would be good to use a more traditional approach to GC but suspect that it’s
more work than we imagine; both developer time and compilation run time.

Mike