chapel-lang/chapel — pull request #165 by ronawho (2014-08-19 03:51:51+00:00)
Title: 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, >= 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