Add V 1.0 of "C for loops"

[Done in collaboration and co-reviewed with @daviditen]

========================
Motivation and Overview:
========================

Previously most of our generated loops were of the form:

i = start;
cond = (i != end);
while (cond) {
  // loop body
  i = i + 1;
  cond = (i != end);
}

where the actual generated code was much uglier. This loop originates from the
these() iterator in ChapelRange.chpl.

The point of this commit is to generate loops of the form:

for (i = start; i <= end; i = i + 1) {
  // loop body
}

There are a couple of motivating reasons for this change. The != relational
operator in the while loop and the way the increment was actually generated
(example is a cleaned up version) meant the back-end compiler couldn't
normalize the loop and thus couldn't perform some optimizations.

We might have been able to clean up the while loop, instead of generating a c
for loop, but well formed c for loops are also required for things like using
OpenACC or OpenMP so it made sense to generate clean c style for loops.

This commit brings us the first version of c for loops (with details about what
will be in V 2.0 below.)

This basic idea is that in ChapelRange.chpl we replace the while loops with a
new primitive "C for loop" and then since most things forward to ranges at the
lowest level we get c for loops in many places.

Some changes are to support building the iterator for the c for loop and
building zippered iterators correctly. Dead code elimination had to be
modified to not kill the test expr of the c for loop and loop invariant code
motion had to be updated to correctly find the pre-header of a c for loop.
Other than that the only real change was adding new codegen functionality for c
for loops and the remaining changes are for things like adding the primitive
itself, and in code that checked for the other loop primitives, the c for loop
is also checked.

This version creates c for loops for non-strided, bounded ranges only. That
happens to be a majority of loops so you still get c for loops in many many
places. V 2.0 will include c for loops for unbounded, and strided iterators.
Additionally iterators over a DefaultRectangular array still use a while loop
because an "optimized" while loop was added a while back in
DefaultRectangular's iterator instead of just forwarding to the range. The only
real reason these other iterators don't use c for loops in this commit is to
make tracking down any potential issues easier.

With this we generate exceptionally clean non-zippered c for loops, and as
clean as we can get zippered iterators without doing de-normalization (though
they are still very clean.)

The current implementation has two regressions because it "breaks" maximal ranges
and positively strided ranges where the high bound is max(idxType) and
negatively strided ranges where the low bound is min(idxType).

=================
Per file changes:
=================

compiler/AST/bb.cpp
 - For c for loops we have to add the init, test, and incr to the basic blocks.
   This is actually pretty simple, and is just based on the semantics of what a
   c for loop is. The init gets executed before the loop, the test gets
   executed before each iteration, and the incr is the last thing that happens
   after the loop body and immediately before the test is done again.

compiler/AST/build.cpp
 - Pretty simple changes. This adds building c for loops. For a c for loop we
   have similar code as for other loops to build up the basic parts of the loop
   and add continue and break labels and such. The main other thing is that
   right now c for loops are of the form:
     __primitive("C for loop", i, start, end, stride)
   In here we take that and actually build up the init, test, and incr exprs
   and effectively create:
     __primitive("C for loop", {i=start}, {i<=end}, {i=i+1})
   Note that in this version the relational operator is forced to be <=. This
   will be updated for V 2.0.

compiler/AST/iterator.cpp
 - Allow C For loops to trigger the isSingleLoopIterator optimization

 - Do not insert the setting of iterator->more for C For loops in zip1 and zip3

 - Adds two new functions to the iterator init, and incr which only get
   populated for C for loops and changes hasMore to behave differently for C for
   loops. For c for loops these functions basically just insert the init, test,
   and incr exprs from the c for loop primitive into the iterator functions.

compiler/include/iterator.h
 -  Just adds the init and incr prototypes

compiler/AST/primitive.cpp
compiler/include/primitive.h
 - Just adds the C_FOR_LOOP primitive

compiler/AST/stmt.cpp
 - These are all just changes to codegen the c for loop. The basic jist is that
   for take each block statement in the c for loop (init, test,incr) and
   codegen them separately and then just insert them into the c for loop
   string.
 - Since c for loops can only contain comma separated statements and not
   regular statements, the real bulk of codegen here is to convert things that
   would normally be code-genned as statements and turn them into comma
   separated statements.

compiler/optimizations/collapseBlocks.cpp
 - We need to collapse the block statements in the c for loop headers since
   each block statement can be composed of multiple block statements sitting
   next to each other for zippered iterators. This puts the logic for
   collapsing CForLoop blocks into a separate function, and also pulls the
   logic to collapse a single block into it's own function to make it easier to
   read.

compiler/optimizations/deadCodeElimination.cpp
 - Do not let expressions in the c for loop header be marked as dead, side
   effect free expressions in deadExpressionElimination. The test in the c for
   loop header is not side effect free, but we didn't have to identify anything
   like this before. The current approach does not eliminate any expressions in
   the header, but I should update it to only not eliminate expressions in the
   test segment that are conditional expressions.

 - Similarly we mark expressions in the header as essential so regular
   deadCodeElmination doesn't get rid of them.

compiler/optimizations/loopInvariantCodeMotion.cpp
 - Updates the helper function in LICM for inserting an expression before the
   loop. The condition/test of the c for loop is identified as the header of
   the loop because of how we build the basic blocks. This is technically
   correct, but when we go to insert we look for the parent of the headers
   first expr and try to insert before that. However for c for loops the test
   is still in the c for loop primitive so we need to go up a few more levels
   to get the actual loop body to insert in to.

compiler/optimizations/optimizeOnClauses.cpp
 - Just adds c for loops to the list of fast primitives

compiler/passes/createTaskFunctions.cpp
 - Just adds c for loops to the list of non parallel block constructs

compiler/resolution/functionResolution.cpp
 - Just adds prototypes and resolved flags to init and incr functions

compiler/resolution/lowerIterators.cpp
 - Changes zippered iterator creation to work with c for loops. All for loops
   are converted to c for loops here. We then put the zip* functions in the
   appropriate place and insert bounds checks if they were turned on. Special
   care had to be taken for dynamically dispatched iterators because they
   create code that cannot be in the c for loop header.

 - The order of this code is pretty delicate. More comments and cleanup will be
   done to this code in V 2.0.

modules/internal/ChapelRange.chpl
 - Splits the these iterator into three iterators: One for strided and bounded
   ranges, one for unbounded ranges, and one for non-strided and bounded
   ranges. Then the non-strided and bounded range was converted to use a "C for
   loop"

 - Removes the check for maximal ranges. What we really want here now is to
   detect when a range will under or over flow. This currently can't be done at
   range construction because in the case of strided ranges, the base range is
   built, and then the by operator is applied to the range so you can get false
   positives. An approach might be to do the checks at iterator time, but that
   means you have to put the same checks in multiple places.
    - Previously ranges such as max(int)-10..max(int) worked because we relied
      on well defined integer overflow semantics (but integer overflow is
      undefined in C) and we relied on the != relational operator in the
      iterator. If you try to generate a c for loop of max(int)-10..max(int)
      you'll end up with something like "for (i=max(int)-10; i<max(int); i++)"
      and that is an infinite loop. This is currently not addressed but V 2.0
      will add checks to warn the user of such cases and provide a different
      (and unfortunately less performant) iterator to use in such cases. This
      iterator should also be able to support maximal ranges.

 - A function withinBounds was added to replace the maximal range checks, but
   it is currently unused. It will be used in V 2.0

test/types/range/diten/cForLoops/simpleRange.chpl
test/types/range/diten/cForLoops/simpleRange.good
test/types/range/diten/cForLoops/userCForLoops.chpl
test/types/range/diten/cForLoops/userCForLoops.good
test/types/range/diten/cForLoops/userDefIter.chpl
test/types/range/diten/cForLoops/userDefIter.good
test/types/range/diten/cForLoops/zipArray.chpl
test/types/range/diten/cForLoops/zipArray.good
test/types/range/diten/cForLoops/zipRange.chpl
test/types/range/diten/cForLoops/zipRange.good
 - Some simple tests to ensure c for loops are working correctly. More will be
   added in V 2.0

test/types/range/hilde/maximalRange.chpl
 - This is a simple change to prevent an infinite loop if we break maximal
   ranges (which I did.)

=================
V 2.0 and beyond:
=================

 - Warnings for ranges with min or max bounds
   - Make this so it can be in the range constructor?
   - And an appropriate iterator to use for these cases
     - As in add an iterator that a user can use for 0:uint..max(uint) or
       max(int)-10..max(int)

 - User defined relational operator for c for loops
   - This should clean up build.cpp
   - C for loops for strided ranges and for unbounded ranges
      - And a clever way to use <, <=, >, >= instead of !=

 - C for loops for Default Rectangular

 - See about removing the isAmbiguous call in ChapelRange iterators?

 - Further clean up codegen (stmt.cpp)
   - Add checks for things that can't be in c for loops
   - Explain why codegenValue is used.

 - Review lower iterators
   - Add note about why we only have one conditional, even with bounds
     checking (or see if that can be addressed)
   - Review dynamically dispatched iterator code

Ideal for V 3.0:
 - Switch to using op= and PRIM_ASSIGN once ref temps are gone
 - Potential iterator/range optimizations:
   - Induction variable elimination
   - Hoist range construction (and merge duplicate ranges)
   - Maybe some way to indicate that the stride is positive or negative
Merge pull request #165 from ronawho/CForLoops-V1

Add V 1.0 of "C for loops"

[Done in collaboration and co-reviewed with @daviditen]

========================
Motivation and Overview:
========================

Previously most of our generated loops were of the form:

i = start;
cond = (i != end);
while (cond) {
  // loop body
  i = i + 1;
  cond = (i != end);
}

where the actual generated code was much uglier. This loop originates from the
these() iterator in ChapelRange.chpl.

The point of this commit is to generate loops of the form:

for (i = start; i <= end; i = i + 1) {
  // loop body
}

There are a couple of motivating reasons for this change. The != relational
operator in the while loop and the way the increment was actually generated
(example is a cleaned up version) meant the back-end compiler couldn't
normalize the loop and thus couldn't perform some optimizations.

We might have been able to clean up the while loop, instead of generating a c
for loop, but well formed c for loops are also required for things like using
OpenACC or OpenMP so it made sense to generate clean c style for loops.

This commit brings us the first version of c for loops (with details about what
will be in V 2.0 below.)

This basic idea is that in ChapelRange.chpl we replace the while loops with a
new primitive "C for loop" and then since most things forward to ranges at the
lowest level we get c for loops in many places.

Some changes are to support building the iterator for the c for loop and
building zippered iterators correctly. Dead code elimination had to be
modified to not kill the test expr of the c for loop and loop invariant code
motion had to be updated to correctly find the pre-header of a c for loop.
Other than that the only real change was adding new codegen functionality for c
for loops and the remaining changes are for things like adding the primitive
itself, and in code that checked for the other loop primitives, the c for loop
is also checked.

This version creates c for loops for non-strided, bounded ranges only. That
happens to be a majority of loops so you still get c for loops in many many
places. V 2.0 will include c for loops for unbounded, and strided iterators.
Additionally iterators over a DefaultRectangular array still use a while loop
because an "optimized" while loop was added a while back in
DefaultRectangular's iterator instead of just forwarding to the range. The only
real reason these other iterators don't use c for loops in this commit is to
make tracking down any potential issues easier.

With this we generate exceptionally clean non-zippered c for loops, and as
clean as we can get zippered iterators without doing de-normalization (though
they are still very clean.)

The current implementation has two regressions because it "breaks" maximal ranges
and positively strided ranges where the high bound is max(idxType) and
negatively strided ranges where the low bound is min(idxType).


=================
Per file changes:
=================

compiler/AST/bb.cpp
 - For c for loops we have to add the init, test, and incr to the basic blocks.
   This is actually pretty simple, and is just based on the semantics of what a
   c for loop is. The init gets executed before the loop, the test gets
   executed before each iteration, and the incr is the last thing that happens
   after the loop body and immediately before the test is done again.

compiler/AST/build.cpp
 - Pretty simple changes. This adds building c for loops. For a c for loop we
   have similar code as for other loops to build up the basic parts of the loop
   and add continue and break labels and such. The main other thing is that
   right now c for loops are of the form:
     __primitive("C for loop", i, start, end, stride)
   In here we take that and actually build up the init, test, and incr exprs
   and effectively create:
     __primitive("C for loop", {i=start}, {i<=end}, {i=i+1})
   Note that in this version the relational operator is forced to be <=. This
   will be updated for V 2.0.

compiler/AST/iterator.cpp
 - Allow C For loops to trigger the isSingleLoopIterator optimization

 - Do not insert the setting of iterator->more for C For loops in zip1 and zip3

 - Adds two new functions to the iterator init, and incr which only get
   populated for C for loops and changes hasMore to behave differently for C for
   loops. For c for loops these functions basically just insert the init, test,
   and incr exprs from the c for loop primitive into the iterator functions.

compiler/include/iterator.h
 -  Just adds the init and incr prototypes

compiler/AST/primitive.cpp
compiler/include/primitive.h
 - Just adds the C_FOR_LOOP primitive

compiler/AST/stmt.cpp
 - These are all just changes to codegen the c for loop. The basic jist is that
   for take each block statement in the c for loop (init, test,incr) and
   codegen them separately and then just insert them into the c for loop
   string.
 - Since c for loops can only contain comma separated statements and not
   regular statements, the real bulk of codegen here is to convert things that
   would normally be code-genned as statements and turn them into comma
   separated statements.

compiler/optimizations/collapseBlocks.cpp
 - We need to collapse the block statements in the c for loop headers since
   each block statement can be composed of multiple block statements sitting
   next to each other for zippered iterators. This puts the logic for
   collapsing CForLoop blocks into a separate function, and also pulls the
   logic to collapse a single block into it's own function to make it easier to
   read.

compiler/optimizations/deadCodeElimination.cpp
 - Do not let expressions in the c for loop header be marked as dead, side
   effect free expressions in deadExpressionElimination. The test in the c for
   loop header is not side effect free, but we didn't have to identify anything
   like this before. The current approach does not eliminate any expressions in
   the header, but I should update it to only not eliminate expressions in the
   test segment that are conditional expressions.

 - Similarly we mark expressions in the header as essential so regular
   deadCodeElmination doesn't get rid of them.

compiler/optimizations/loopInvariantCodeMotion.cpp
 - Updates the helper function in LICM for inserting an expression before the
   loop. The condition/test of the c for loop is identified as the header of
   the loop because of how we build the basic blocks. This is technically
   correct, but when we go to insert we look for the parent of the headers
   first expr and try to insert before that. However for c for loops the test
   is still in the c for loop primitive so we need to go up a few more levels
   to get the actual loop body to insert in to.

compiler/optimizations/optimizeOnClauses.cpp
 - Just adds c for loops to the list of fast primitives

compiler/passes/createTaskFunctions.cpp
 - Just adds c for loops to the list of non parallel block constructs

compiler/resolution/functionResolution.cpp
 - Just adds prototypes and resolved flags to init and incr functions

compiler/resolution/lowerIterators.cpp
 - Changes zippered iterator creation to work with c for loops. All for loops
   are converted to c for loops here. We then put the zip* functions in the
   appropriate place and insert bounds checks if they were turned on. Special
   care had to be taken for dynamically dispatched iterators because they
   create code that cannot be in the c for loop header.

 - The order of this code is pretty delicate. More comments and cleanup will be
   done to this code in V 2.0.

modules/internal/ChapelRange.chpl
 - Splits the these iterator into three iterators: One for strided and bounded
   ranges, one for unbounded ranges, and one for non-strided and bounded
   ranges. Then the non-strided and bounded range was converted to use a "C for
   loop"

 - Removes the check for maximal ranges. What we really want here now is to
   detect when a range will under or over flow. This currently can't be done at
   range construction because in the case of strided ranges, the base range is
   built, and then the by operator is applied to the range so you can get false
   positives. An approach might be to do the checks at iterator time, but that
   means you have to put the same checks in multiple places.
    - Previously ranges such as max(int)-10..max(int) worked because we relied
      on well defined integer overflow semantics (but integer overflow is
      undefined in C) and we relied on the != relational operator in the
      iterator. If you try to generate a c for loop of max(int)-10..max(int)
      you'll end up with something like "for (i=max(int)-10; i<max(int); i++)"
      and that is an infinite loop. This is currently not addressed but V 2.0
      will add checks to warn the user of such cases and provide a different
      (and unfortunately less performant) iterator to use in such cases. This
      iterator should also be able to support maximal ranges.

 - A function withinBounds was added to replace the maximal range checks, but
   it is currently unused. It will be used in V 2.0

test/types/range/diten/cForLoops/simpleRange.chpl
test/types/range/diten/cForLoops/simpleRange.good
test/types/range/diten/cForLoops/userCForLoops.chpl
test/types/range/diten/cForLoops/userCForLoops.good
test/types/range/diten/cForLoops/userDefIter.chpl
test/types/range/diten/cForLoops/userDefIter.good
test/types/range/diten/cForLoops/zipArray.chpl
test/types/range/diten/cForLoops/zipArray.good
test/types/range/diten/cForLoops/zipRange.chpl
test/types/range/diten/cForLoops/zipRange.good
 - Some simple tests to ensure c for loops are working correctly. More will be
   added in V 2.0

test/types/range/hilde/maximalRange.chpl
 - This is a simple change to prevent an infinite loop if we break maximal
   ranges (which I did.)


=================
V 2.0 and beyond:
=================

 - Warnings for ranges with min or max bounds
   - Make this so it can be in the range constructor?
   - And an appropriate iterator to use for these cases
     - As in add an iterator that a user can use for 0:uint..max(uint) or
       max(int)-10..max(int)

 - User defined relational operator for c for loops
   - This should clean up build.cpp
   - C for loops for strided ranges and for unbounded ranges
      - And a clever way to use <, <=, >, >= instead of !=

 - C for loops for Default Rectangular

 - See about removing the isAmbiguous call in ChapelRange iterators?

 - Further clean up codegen (stmt.cpp)
   - Add checks for things that can't be in c for loops
   - Explain why codegenValue is used.

 - Review lower iterators
   - Add note about why we only have one conditional, even with bounds
     checking (or see if that can be addressed)
   - Review dynamically dispatched iterator code

Ideal for V 3.0:
 - Switch to using op= and PRIM_ASSIGN once ref temps are gone
 - Potential iterator/range optimizations:
   - Induction variable elimination
   - Hoist range construction (and merge duplicate ranges)
   - Maybe some way to indicate that the stride is positive or negative