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 3:21 PM, Elliot Ronaghan <notifications@github.com<mailto:notifications@github.com>> wrote:


In compiler/AST/ForLoop.cpp<https://github.com/chapel-lang/chapel/pull/1021#discussion-diff-22013493>:

> +      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()));


Ok phew, yeah, you're right. I was just thinking about how we clean the global vectors, but that happens after the process you just described.

—
Reply to this email directly or view it on GitHub<https://github.com/chapel-lang/chapel/pull/1021/files#r22013493>.



Hmmm.  I added a note on github but I haven’t received an email with the contents.  Just in case, here’s a slightly
edited version of what I said



I am not as comfortable with cleanAst() et al as I'd like but I don't
think that this recent discussion is quite right.  I don't think there's
any "marking of nodes" as dead and I have never noticed any
reachability algorithm. I may be using these terms differently from
others due to the notions I have about garbage collectors and
mark/sweep collectors in particular.

It's closer to what Elliot says. CleanAST walks each of the g<Type>
lists and applies the isAlive() test to each node in the list.  The
details of that test vary a little based on the broad AST category,
(expr vs type vs symbol) but many nodes are viewed as not alive if
they do not have a parentExpr.

One funny thing that I still haven't completely nailed down is the
business logic for setting and clearing parentExpr and parentSymbol. I
think replace() is responsible for the most common cases but some
nodes get inserted in to trees without replace() and yet still get
their parent set before the next run of cleanAst() runs; I think
because of recursive application of replace() that sweep up the cases
that I would be nervous about.

I do worry about scenarios in which multiple nodes have the same
parentExpr but for which the parent thinks only one of the nodes is a
child e.g. by directly assigning a field in a node rather than causing
replaceChild to be invoked. I've questioned myself several times recently
due to the refactoring of the Loop nodes.  We have a lot of business
logic that relies on walking up from leaves and so (a) we're getting
lucky (b) we've being careful (c) there's some other magic going on
that I haven't noticed.